Parity of Operation Length Sum

In this problem, you are given two integer sequences a and b of length n. Initially, sequence a is given, and then m operations are performed on a to obtain sequence b.

For each operation, two indices l and r (with 1 ≤ l ≤ r ≤ n) are chosen. For every index i in the range [l, r], the following value is added to a_i:

\[ \digamma(i-l+1) \]

The sequence \(\digamma(x)\) is defined as follows:

\[ \digamma(x)=\{1,1,-1,-1,1,1,-1,-1,\ldots\} \]

It is periodic with a minimum period of \(T=4\), meaning that \(\digamma(1)=1\), \(\digamma(2)=1\), \(\digamma(3)=-1\), \(\digamma(4)=-1\), and then it repeats.

In each operation, the length of the chosen interval, \(len = r-l+1\), is recorded. Let \(sum = \sum_{j=1}^{m} len_j\) be the total sum of these lengths. Unfortunately, the list of interval lengths and their total sum are lost, and only the initial sequence a and the resulting sequence b remain.

Your task is to determine the parity (i.e., the value modulo 2) of \(sum\). Note that it can be shown that:

\[ \sum_{j=1}^{m} \digamma(len_j) \equiv \sum_{j=1}^{m} len_j\pmod{2} \]

Thus, by calculating

\[ S = \sum_{i=1}^{n} (b_i - a_i), \]

you will have \(S \bmod 2 = sum \bmod 2\).

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵) representing the length of the sequences.

The second line contains n integers denoting the initial sequence a.

The third line contains n integers denoting the resulting sequence b after all operations.

outputFormat

Output a single integer which is the value of \(sum \bmod 2\).

sample

4
0 0 0 0
1 1 -1 -1

0