P9086 "SvR-2" A Tricky Range Operation Problem.

**Problem Number:** $\textit{45}$ As everyone knows, range operation problems usually ask for values like range sums, maximums, and so on. But today, Little F has an unusual request.

Little F is studying the [Fibonacci sequence](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0). To his surprise, by slightly modifying the definition of the Fibonacci sequence $F$, he obtains the $\digamma$ sequence: $$\digamma(x)=\{1,1,-1,-1,1,1,-1,-1,1,\ldots\}$$ Note that the $\digamma$ sequence is periodic, with the smallest positive period $T=4$. Please note the difference between this $\digamma$ sequence and the [double gamma function](https://zh.wikipedia.org/wiki/%E5%8F%8C%E4%BC%BD%E7%8E%9B%E5%87%BD%E6%95%B0) in mathematics that uses the same symbol. Little F finds a sequence $a$ of length $n$. Each time, he performs the following operation: - Choose two integers $l, r$ such that $1\le l\le r\le n$. - For each $i$ satisfying $l\le i\le r$, add $\digamma(i-l+1)$ to $a_i$. - Record the length of the chosen interval for this operation (i.e. the $j$-th operation) as $len_j=r-l+1$. He performs a total of $m$ operations. Let the resulting sequence after all operations be $b$, and let $sum=\sum_{i=1}^m len_i$. Unfortunately, Little F loses both $sum$ and the sequence $len$. He only remembers $n$ and the sequences $a, b$. Now, he wants you to determine the **parity** of $sum$, **that is, the value of $\textbf{\textit{sum}}$ modulo $\textbf2$**.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. The next $3\cdot T$ lines describe the test cases. For each test case: - The first line contains an integer $n$. - The second line contains $n$ integers describing the sequence $a$. - The third line contains $n$ integers describing the sequence $b$. **It is guaranteed that sequence $a$ can be transformed into sequence $b$ by some number of operations.**

For each test case, output one line with a single number, which is $sum$ modulo $2$.

#### Explanation of Sample 1 Note that the following operations may have been performed: - In the $1$-st operation, choose $l=2, r=3$, then the sequence becomes $[1,{\underline{\color{red}\textbf{3}}},{\underline{\color{red}\textbf{4}}},4]$. At this time, $len_1=2$. - In the $2$-nd operation, choose $l=1, r=3$, then the sequence becomes $[{\underline{\color{red}\textbf{2}}},{\underline{\color{red}\textbf{4}}},{\underline{\color{red}\textbf{3}}},4]$. At this time, $len_2=3$. Then $sum=len_1+len_2=5$, which is odd. Therefore, $sum\bmod 2=1$. #### Constraints and Conventions **This problem uses bundled testdata.** $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{\sum n\le} & \textbf{Special Properties} & \textbf{Score} \\\hline \textsf{1} & \le 10 & a_i,b_i\le 10^9 & 10 \\\hline \textsf{2} & \le 10^3 & a_i,b_i\le 10^9 & 20 \\\hline \textsf{3} & \text{No special constraints} & a_i,b_i\le 10^9 & 20 \\\hline \textsf{4} & \text{No special constraints} & a_i\le b_i & 20 \\\hline \textsf{5} & \text{No special constraints} & - & 30 \\\hline\hline \end{array} $$ For $100\%$ of the testdata, $1\le T\le 10^3$, $1\le n\le 10^5$, $1\le a_i,b_i\le 10^{18}$. Within a single test point, it is guaranteed that $\sum n\le 2\times 10^5$. #### Notes The $\digamma$ sequence has the following recurrence: $$ \digamma(x)= \begin{cases} 1,&x\le 2\\ -1,&x=3\\ \digamma(x-1)-\digamma(x-2)+\digamma(x-3),&x>3. \end{cases} $$ Translated by ChatGPT 5