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

**Problem Number:** $\textit{45}$ 众所周知，区间操作问题应该求出区间和、最大值等值。但今天小 F 有个不情之请。

小 F 正在研究[斐波那契数列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0)，他惊讶地发现，可以把这种数列 $F$ 的定义式略作修改，得到 $\digamma$ 数列： $$\digamma(x)=\{1,1,-1,-1,1,1,-1,-1,1,\ldots\}$$ 注意到 $\digamma$ 数列具有周期性，最小正周期 $T=4$。 请注意这里 $\digamma$ 数列与数学上用其表示的[双伽玛函数](https://zh.wikipedia.org/wiki/%E5%8F%8C%E4%BC%BD%E7%8E%9B%E5%87%BD%E6%95%B0)的区别。 小 F 找到一个长度为 $n$ 的数列 $a$，他每次对其进行如下操作： - 选定两个整数 $l,r$，满足 $1\le l\le r\le n$。 - 对于每个满足 $l\le i\le r$ 的 $i$，将 $a_i$ 加上 $\digamma(i-l+1)$。 - 记录下本次操作（即第 $j$ 次操作）的选定区间的长度 $len_j=r-l+1$。 他一共进行了 $m$ 次操作，操作后得到数列记作 $b$，同时记 $sum=\sum_{i=1}^mlen_i$。 不幸的是，小 F 把 $sum$ 和数列 $len$ 都弄丢了，他只记得 $n$ 和数列 $a,b$。 现在，他想请你根据这些信息，求出 $sum$ 的**奇偶**，**即 $\textbf{\textit{sum}}$ 对 $\textbf2$ 取模后的值**。

无

无

#### 样例 1 说明 注意到可能进行的是如下操作： - 第 $1$ 次操作选定 $l=2,r=3$，则数列变成 $[1,{\underline\color{red}\textbf3},{\underline\color{red}\textbf4},4]$。此时 $len_1=2$。 - 第 $2$ 次操作选定 $l=1,r=3$，则数列变成 $[{\underline\color{red}\textbf2},{\underline\color{red}\textbf4},{\underline\color{red}\textbf3},4]$。此时 $len_2=3$。 则 $sum=len_1+len_2=5$，是奇数。故 $sum\bmod 2=1$。 #### 数据规模与约定 **本题采用捆绑测试** $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{\sum n\le} & \textbf{特殊性质} & \textbf{分值} \\\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{无特殊限制} & a_i,b_i\le 10^9 & 20 \\\hline \textsf{4} & \text{无特殊限制} & a_i\le b_i & 20 \\\hline \textsf{5} & \text{无特殊限制} & - & 30 \\\hline\hline \end{array} $$ 对于 $100\%$ 的数据，有 $1\le T\le 10^3$，$1\le n\le 10^5$，$1\le a_i,b_i\le 10^{18}$。 单个测试点内保证 $\sum n\le 2\times 10^5$。 #### 说明 $\digamma$ 数列拥有如下的递推式： $$ \digamma(x)= \begin{cases} 1,&x\le 2\\ -1,&x=3\\ \digamma(x-1)-\digamma(x-2)+\digamma(x-3),&x>3. \end{cases} $$