Binary String

You are given a binary string $S$ of length $n$, consisting only of 0 and 1.

The indices of $S$ start from 1. $S[a : b]$ denotes the substring of $S$ from index $a$ to index $b$, inclusive.

You apply the following insertion operation $m$ times. Each operation takes two integers $x \le y$, and the values of $x$ and $y$ may differ between operations.

• The inserted string is the complement of $S[x : y]$, meaning every 0 becomes 1 and every 1 becomes 0.
• The string is inserted immediately after the $y$-th character of $S$. After the insertion, the length of $S$ grows by $y - x + 1$.
• $S$ is updated after each operation. The next operation uses the updated $S$.

The goal is to find the first $k$ characters of the final $S$ after all $m$ operations.

For example, let $S = 01010110$, $n = 8$, $m = 2$, $k = 12$, and apply the operations $(x = 2, y = 4)$ and $(x = 3, y = 5)$ in order. The first operation inserts the complement of $S[2 : 4] = 101$, which gives S = 01010100110 (the bold part is the inserted text). The second operation inserts the complement of $S[3 : 5] = 010$, which gives S = 01010101100110. Since $k = 12$, the answer is the first 12 characters, 010101011001.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case contains $n$, $m$, and $k$, separated by spaces.

The second line contains the binary string of length $n$.

Each of the next $m$ lines contains two integers $x_i$ and $y_i$. It is guaranteed that $1 \le x_i \le y_i \le$ min(the length of $S$ just before the $i$-th operation, $10^{12}$).

Also, $k$ does not exceed the smaller of the length of the final $S$ and $10^6$.

For each test case, print the string of length $k$ on one line.

• Case 2: 1010 becomes 10010. Since $k = 4$, only the first 4 characters are printed.
• Case 3: 10101100 becomes 1001101100, and then 10011011110010000. Since $k = 16$, only the first 16 characters are printed.