#2032. 「SvR-2」令人为难的区间操作问题

「SvR-2」令人为难的区间操作问题

题目描述

小 F 正在研究斐波那契数列,他惊讶地发现,可以把这种数列 FF 的定义式略作修改,得到 ϝ\digamma 数列:

ϝ(x)={1,1,−1,−1,1,1,−1,−1,1,…}\digamma(x)=\{1,1,-1,-1,1,1,-1,-1,1,\ldots\}

注意到 ϝ\digamma 数列具有周期性,最小正周期 T=4T=4。

请注意这里 ϝ\digamma 数列与数学上用其表示的双伽玛函数的区别。

小 F 找到一个长度为 nn 的数列 aa,他每次对其进行如下操作:

  • 选定两个整数 l,rl,r,满足 1≤l≤r≤n1\le l\le r\le n。
  • 对于每个满足 l≤i≤rl\le i\le r 的 ii,将 aia_i 加上 ϝ(i−l+1)\digamma(i-l+1)。
  • 记录下本次操作(即第 jj 次操作)的选定区间的长度 lenj=r−l+1len_j=r-l+1。

他一共进行了 mm 次操作,操作后得到数列记作 bb,同时记 sum=∑i=1mlenisum=\sum_{i=1}^mlen_i。

不幸的是,小 F 把 sumsum 和数列 lenlen 都弄丢了,他只记得 nn 和数列 a,ba,b。

现在,他想请你根据这些信息,求出 sumsum 的奇偶,即 sum\textbf{\textit{sum}} 对 2\textbf2 取模后的值。

输入格式

本题有多组数据。

第一行一个整数 TT,表示数据组数。

接下来 3⋅T3\cdot T 行,描述每组数据。对于每组数据:

  • 第一行一个整数 nn。
  • 第二行 nn 个整数,描述数列 aa。
  • 第三行 nn 个整数,描述数列 bb。

数据保证数列 aa 一定可以经过若干操作变为数列 bb。

输出格式

对于每组数据,输出仅一行一个数,即 sumsum 对 22 取模后的值。

样例

1
4
1 2 3 4
2 4 3 4
1

题目来源:洛谷 P9086