Person in Charge

• SleepingCup

Problem Description

For a binary string $S = s_1 \ldots s_n$ of length $n\ (n \ge 3)$, define the transformation $T = f(S) = t_1 \ldots t_n$ as follows:

$$t_i = \begin{cases} s_i, & i \le 2, \\ s_i, & i \ge 3 \text{ and } s_{i-2} = 0, \\ s_{i-1}, & i \ge 3 \text{ and } s_{i-2} = 1. \end{cases}$$

A fixed point of the transformation $f$ is defined as follows: if a binary string $T$ satisfies $f(T) = T$, then $T$ is called a fixed point of $f$.

Let $f^k(S)$ denote the string obtained by applying the transformation $f$ $k$ times to $S$. Specifically, let $f^0(S) = S$. Find the smallest natural number $k$ such that $f^k(S)$ is a fixed point of $f$, i.e., the smallest natural number $k$ satisfying $f^{k+1}(S) = f^k(S)$. It can be proven that such a $k$ always exists.

Little Z found this problem too simple, so he added $q$ modification operations. The $i$-th ($1 \le i \le q$) modification is given by two positive integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$), which flips all bits in the interval $[l_i, r_i]$ (i.e., 0 becomes 1 and 1 becomes 0). For the initial string and after each modification, you need to find the smallest natural number $k$ such that $f^k(S)$ is a fixed point of $f$.

Input Format

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c, t$, representing the test case number and the number of test cases, respectively. $c = 0$ indicates that this test case is a sample.

For each test case:

The first line contains two positive integers $n, q$, representing the length of $S$ and the number of modifications, respectively.

The second line contains a binary string $S = s_1 \ldots s_n$ of length $n$, representing the initial string.

The $(i + 2)$-th line ($1 \le i \le q$) contains two positive integers $l_i, r_i$, representing a modification operation.

Output Format

For each test case, let $k_0$ be the answer for the initial string and $k_i$ ($1 \le i \le q$) be the answer after the $i$-th modification. Output a single positive integer, which is $\oplus_{i=0}^{q} ((i + 1) \times k_i)$, where $\oplus$ denotes the bitwise XOR operation.

Samples

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

2
4

Sample 1 Explanation

This sample contains two test cases.

For the first test case:

• Initially, $S = 11010$, $f(S) = 11100$, $f^2(S) = 11110$, $f^3(S) = f^4(S) = 11111$, so $k_0 = 3$;
• After the first modification, $S = 11110$, $f(S) = f^2(S) = 11111$, so $k_1 = 1$;
• After the second modification, $S = 10110$, $f(S) = f^2(S) = 10011$, so $k_2 = 1$.

Thus, the answer is $\bigoplus_{i=0}^{q} ((i+1) \times k_i) = (1 \times 3) \oplus (2 \times 1) \oplus (3 \times 1) = 3 \oplus 2 \oplus 3 = 2$.

For the second test case:

• Initially, $S = 1010100$, $k_0 = 1$;
• After the first modification, $S = 1010101$, $k_1 = 1$;
• After the second modification, $S = 1101101$, $k_2 = 5$;
• After the third modification, $S = 0001101$, $k_3 = 2$.

Thus, the answer is $\bigoplus_{i=0}^{q} ((i+1) \times k_i) = (1 \times 1) \oplus (2 \times 1) \oplus (3 \times 5) \oplus (4 \times 2) = 4$.

Sample 2

See the files ternary/ternary2.in and ternary/ternary2.ans in the contestant directory.

This sample satisfies the constraints of test cases $1 \sim 3$.

Sample 3

See the files ternary/ternary3.in and ternary/ternary3.ans in the contestant directory.

This sample satisfies the constraints of test cases $4 \sim 6$.

Sample 4

See the files ternary/ternary4.in and ternary/ternary4.ans in the contestant directory.

This sample satisfies the constraints of test cases $13,14$.

Sample 5

See the files ternary/ternary5.in and ternary/ternary5.ans in the contestant directory.

This sample satisfies the constraints of test cases $17 \sim 19$.

Data Range

Let $N, Q$ be the sums of $n, q$ across all test cases in a single test point. For all test cases, it is guaranteed:

• $1 \le t \le 5$;
• $3 \le n \le 4 \times 10^5$, $N \le 8 \times 10^5$;
• $1 \le q \le 4 \times 10^5$, $Q \le 8 \times 10^5$;
• For all $1 \le i \le n$, $s_i \in \{0, 1\}$;
• For all $1 \le i \le q$, $1 \le l_i \le r_i \le n$.

Test Case	$n, q \le$	$N, Q \le$	Special Properties
$1 \sim 3$	$200$	$10^3$	A
$4 \sim 6$			None
$7, 8$	$5,000$	$10^4$	A
$9 \sim 11$			None
$12$	$10^5$	$2 \times 10^5$	A
$13, 14$			B
$15, 16$			None
$17 \sim 19$	$4 \times 10^5$	$8 \times 10^5$	C
$20$			None

• Special Property A: The initial string and each modified string have a position $p \in [2, n]$ such that $s_1 = s_2 = \cdots = s_p = 1$ and $s_{p+1} = \cdots = s_n = 0$.
• Special Property B: For all $1 \le i \le q$, $l_i = 1$ and $r_i = n$.
• Special Property C: For all $1 \le i \le q$, $l_i = 1$ and $r_1 \le r_2 \le \cdots \le r_q$.