对于一个长度为 n (n \geq 3) 的 01 串 S = s_1 \ldots s_n,定义变换 T = f(S) = t_1 \ldots t_n 如下:
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 的不动点。