A93184.「NOI2025」三目运算符

对于一个长度为 $n$ $(n \geq 3)$ 的 $01$ 串 $S = s_1 \ldots s_n$，定义变换 $T = f(S) = t_1 \ldots t_n$ 如下：

$$t_i = \begin{cases} s_i, & i \leq 2, \\ s_i, & i \geq 3 \text{ 且 } s_{i-2} = 0, \\ s_{i-1}, & i \geq 3 \text{ 且 } s_{i-2} = 1. \end{cases}$$

定义变换 $f$ 的不动点如下：若 $01$ 串 $T$ 满足 $f(T) = T$，则称 $T$ 为变换 $f$ 的不动点。

记 $f^k(S)$ 为 $S$ 经过 $k$ 次变换得到的串。特别地，记 $f^0(S) = S$。求最小的自然数 $k$，使得 $f^k(S)$ 为变换 $f$ 的不动点，即满足 $f^{k+1}(S) = f^k(S)$ 的最小的自然数 $k$。可以证明，一定存在自然数 $k$ 使得 $f^k(S)$ 为变换 $f$ 的不动点。

小 Z 觉得这个问题过于简单，因此他增加了 $q$ 次修改操作。第 $i$ $(1 \leq i \leq q)$ 次修改会给定两个正整数 $l_i, r_i$ $(1 \leq l_i \leq r_i \leq n)$，然后将区间 $[l_i, r_i]$ 内的所有原有的 $0$ 替换为 $1$，所有原有的 $1$ 替换为 $0$。你需要对初始时及每次修改后的字符串 $S$，求出最小的自然数 $k$，使得 $f^k(S)$ 为变换 $f$ 的不动点。

从文件 ternary.in 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含两个正整数 $n, q$，分别表示 $S$ 的长度和修改次数。

第二行包含一个长度为 $n$ 的 $01$ 串 $S = s_1 \ldots s_n$，表示初始时的字符串。

第 $i + 2$ $(1 \leq i \leq q)$ 行包含两个正整数 $l_i, r_i$，表示一次修改操作。

输出到文件 ternary.out 中。

对于每组测试数据，设初始时的答案为 $k_0$，第 $i$ $(1 \leq i \leq q)$ 次修改后的答案为 $k_i$，输出一行一个正整数，表示 $\oplus_{i=0}^{q} ((i + 1) \times k_i)$，其中 $\oplus$ 表示二进制按位异或。