Helter Skelter

A non-empty string is called a binary string if it consists only of the characters '0' and '1'. A substring $s[l \ldots r]$ $(1 \le l \le r \le |s|)$ of a string $s = s_1 s_2 \ldots s_{|s|}$ is the string $s_l s_{l+1} \ldots s_r$.

Professor Zhang has a long binary string $s$ that starts with '0'. He wants to know whether $s$ has a substring with exactly $a$ zeros and exactly $b$ ones, where $a$ and $b$ are two given integers.

The string is very long, so it is compressed as follows.

• Split the string into runs of equal consecutive characters.
• Any two adjacent runs consist of different characters. Write the length of each run to represent the string.

For example, the runs of the binary string 00101100011110111101001111111 are $\{00, 1, 0, 11, 000, 1111, 0, 1111, 0, 1, 00, 1111111\}$, so it is compressed into $\{2, 1, 1, 2, 3, 4, 1, 4, 1, 1, 2, 7\}$.

The first line contains an integer $T$, the number of test cases. For each test case, the first line contains two integers $n$ and $m$ ($1 \le n \le 1000$, $1 \le m \le 5 \cdot 10^5$), the number of runs and the number of queries. The next line contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1 \le x_i \le 10^6$), the length of each run.

Each of the following $m$ lines contains two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le |s|$, $1 \le a_i + b_i \le |s|$). For each query, determine whether $s$ has a substring with exactly $a_i$ zeros and exactly $b_i$ ones.

There are at most 200 test cases, and the total input size is at most 20 mebibytes. The sum of $m$ over all test cases is at most $2 \cdot 10^6$.

For each test case, print a binary string of length $m$. The $i$-th digit is '1' if the answer to the $i$-th query is yes, and '0' otherwise.