题目描述

对于一个长度为 $n$（$n \geq 3$）的 01 串 $S = s_1 \dots s_n$，定义变换 $T = f(S) = t_1 \dots t_n$（题目未明确变换 $f$ 具体规则，结合样例推测为特定逻辑变换）。定义变换 $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$。

小 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$。

输入格式

1. 第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数，$c = 0$ 表示该测试点为样例。
2. 每组测试数据：
   • 第一行包含两个正整数 $n, q$，分别表示 $S$ 的长度和修改次数。
   • 第二行包含一个长度为 $n$ 的 01 串 $S = s_1 \dots s_n$，表示初始时的字符串。
   • 第 $i + 2$（$1 \leq i \leq q$）行包含两个正整数 $l_i, r_i$，表示一次修改操作。

输出格式

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

样例1

输入

0 2
5 2
11010
3 3
2 2
7 3
1010100
7 7
2 4
1 2

输出

2
4

样例1解释

该样例共包含两组测试数据：

1. 第一组测试数据：
   • 初始时，$S = 11010$，$f(S) = 11100$，$f^2(S) = 11110$，$f^3(S) = f^4(S) = 11111$，因此 $k_0 = 3$。
   • 第一次操作后，$S = 11110$，$f(S) = f^2(S) = 11111$，因此 $k_1 = 1$。
   • 第二次操作后，$S = 10110$，$f(S) = f^2(S) = 10011$，因此 $k_2 = 1$。
   • 答案为 $(1 \times 3) \oplus (2 \times 1) \oplus (3 \times 1) = 3 \oplus 2 \oplus 3 = 2$。
2. 第二组测试数据：
   • 初始时，$S = 1010100$，$k_0 = 1$。
   • 第一次操作后，$S = 1010101$，$k_1 = 1$。
   • 第二次操作后，$S = 1101101$，$k_2 = 5$。
   • 第三次操作后，$S = 0001101$，$k_3 = 2$。
   • 答案为 $(1 \times 1) \oplus (2 \times 1) \oplus (3 \times 5) \oplus (4 \times 2) = 4$。

数据范围

• $3 \leq n \leq 4 \times 10^5$，$1 \leq q \leq 4 \times 10^5$。
• 设 $N, Q$ 分别为单个测试点内所有测试数据的 $n, q$ 的和，$N \leq 8 \times 10^5$，$Q \leq 8 \times 10^5$。
• 对于所有 $1 \leq i \leq n$，均有 $s_i \in \{0, 1\}$。
• 对于所有 $1 \leq i \leq q$，均有 $1 \leq l_i \leq r_i \leq n$。

特殊性质说明：

• A：保证初始时及每次修改后，存在整数 $p \in [2, n]$ 满足 $s_1 = s_2 = \cdots = s_p = 1$ 且 $s_{p+1} = \cdots = s_n = 0$。
• B：保证对于所有 $1 \leq i \leq q$，均有 $l_i = 1$，$r_i = n$。
• C：保证对于所有 $1 \leq i \leq q$，均有 $l_i = 1$，且 $r_1 \leq r_2 \leq \cdots \leq r_q$。