Background

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.

Problem Description

Little F is studying the Fibonacci sequence. 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 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$.

Input Format

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.

Output Format

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

1
4
1 2 3 4
2 4 3 4

1

Hint

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