시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1 1 1 100.000%

문제

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

Professor Zhang has got a long binary string $s$ starting with '0', and he wants to know whether there is a substring of $s$ such that the number of occurrences of '0' and '1' in this substring are exactly $a$ and $b$, respectively, where $a$ and $b$ are two given integers.

Since the binary string is very long, we will compress it. The compression method is as follows:

  • Split the string into runs of equal consecutive characters.
  • Any two adjacent runs consist of different characters. Use 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 will be compressed into $\{2, 1, 1, 2, 3, 4, 1, 4, 1, 1, 2, 7\}$.

입력

There are multiple test cases. The first line of input contains an integer $T$, indicating 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$) indicating 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|$) which means that Professor Zhang wants to know whether there is a substring of $s$ such that the number of occurrences of '0' and '1' in this substring are exactly $a_i$ and $b_i$, respectively.

There are no more than $200$ test cases, and the total size of the input is at most $20$ mebibytes. Additionally, the sum of $m$ in 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 must be '1' if the answer for the $i$-th query is "yes", or '0' otherwise.

예제 입력 1

3
2 3
3 4
3 0
3 4
1 2
3 4
1 2 3
5 1
4 2
1 3
3 2
12 10
2 1 1 2 3 4 1 4 1 1 2 7
2 1
2 2
2 3
2 4
2 5
4 1
4 2
4 3
4 4
4 5

예제 출력 1

111
0101
1111101111