10809.三目运算符(ternary)

对于一个长度为n(n之3)的01串S=s₁...s_n，定义变换T=f(S)=t₁...t_n如下: 定义变换f的不动点如下:若01串T满足f(T)=T,则称T为变换f的不动点。 记f^k(S)为S经过k次变换得到的串。特别地，记f⁰(S)=S。求最小的自然数 k，使得 f^k(S)为变换f的不动点，即满足 f^k+1(S)=f^k(S)的最小的自然数k。可以证明, 一定存在自然数k使得f^k(S)为变换f的不动点。 小Z觉得这个问题过于简单，因此他增加了q次修改操作。第i(1≤i<g)次修改会给定两个正整数l_i,k_i(1≤l_i≤r_i≤n)，然后将区间[r,l]内的所有原有的0替换为1，所有原有的1替换为0。你需要对初始时及每次修改后的字符串S，求出最小的自然数k，使得f^k(S)为变换f的不动点。

从文件termary.in 中读入数据。 本题包含多组测试数据。 输入的第一行包含两个非负整数ct，分别表示测试点编号与测试数据组数。c=0表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据: 第一行包含两个正整数n,q，分别表示S的长度和修改次数。 第二行包含一个长度为n的01串S=s₁...s_n，表示初始时的字符串。 第i+2(1≤i≤q)行包含两个正整数l_i,r_i,表示一次修改操作。

输出到文件 ternary.out 中。 对于每组测试数据，设初始时的答案为k₀，第i(1<i<q)次修改后的答案为k_i输出一行一个正整数，表示⊕^q_i=0((i+1)×k;)，其中⊕表示二进制按位异或。

【样例1解释】 该样例共包含两组测试数据。 对于第一组测试数据: 初始时，S=11010，f(S)=11100，f²(S)=11110，f³(S)=f⁴(S)=11111，因此k₀=3: 第一次操作后，S=11110，f(S)=f²(S)=11111，因此k₁=1; 第二次操作后，S=10110，f(S)=f²(S)=10011，因此k₂=1。 故答案为⊕^q_i=0((i+1)×k_i)=(1x3)⊕(2x1)⊕(3x1)=3⊕2⊕3=2.对于第二组测试数据: 初始时，S=1010100，k₀=1; 第一次操作后，S=1010101，k₁=1; 第二次操作后，S=1101101，k₂=5: 第三次操作后，S=0001101，k₃=2。 故答案为⊕^q_i=0((i+1)×k_i)=(1x1)⊕(2x1)⊕(3x5)⊕(4x2)=4。

【样例 2】 见选手目录下的ternary/terary2.in与ternary/ternary2.ans.该样例满足测试点1~3的约束条件。

【样例 3】 见选手目录下的ternary/ternary3.in与ternary/ternary3.ans. 该样例满足测试点4~6的约束条件。

【样例 4】 见选手目录下的 ternary/ternary4.in与ternary/ternary4.ans。 该样例满足测试点13，14的约束条件。

【样例 5】 见选手目录下的 ternary/ternary5.in与ternary/ternary5.ans该样例满足测试点17~19的约束条件。

【数据范围】