헬터 스켈터

이진 문자열은 '0'과 '1'로만 이루어진 비어 있지 않은 문자열이다. 문자열 $s = s_1 s_2 \ldots s_{|s|}$의 부분 문자열 $s[l \ldots r]$ $(1 \le l \le r \le |s|)$은 $s_l s_{l+1} \ldots s_r$을 뜻한다.

장 교수는 '0'으로 시작하는 긴 이진 문자열 $s$를 가지고 있다. 그는 $s$의 부분 문자열 중에 '0'이 정확히 $a$개, '1'이 정확히 $b$개 들어 있는 것이 있는지 알고 싶다. 여기서 $a$와 $b$는 주어지는 두 정수이다.

문자열이 매우 길어서 다음 방식으로 압축한다.

• 같은 문자가 연속으로 나오는 구간으로 문자열을 나눈다.
• 인접한 두 구간의 문자는 서로 다르다. 각 구간의 길이를 차례로 적어 문자열을 나타낸다.

예를 들어 이진 문자열 00101100011110111101001111111의 구간은 $\{00, 1, 0, 11, 000, 1111, 0, 1111, 0, 1, 00, 1111111\}$이며, 이는 $\{2, 1, 1, 2, 3, 4, 1, 4, 1, 1, 2, 7\}$로 압축된다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 구간의 개수 $n$과 질의의 개수 $m$이 주어진다($1 \le n \le 1000$, $1 \le m \le 5 \cdot 10^5$).

다음 줄에는 각 구간의 길이 $x_1, x_2, \ldots, x_n$이 주어진다($1 \le x_i \le 10^6$).

이어서 $m$개의 줄에 두 정수 $a_i$와 $b_i$가 한 줄에 하나씩 주어진다($0 \le a_i, b_i \le |s|$, $1 \le a_i + b_i \le |s|$). 각 질의는 '0'이 정확히 $a_i$개, '1'이 정확히 $b_i$개인 부분 문자열이 $s$에 있는지 묻는다.

테스트 케이스는 최대 200개이며, 전체 입력 크기는 20 MiB 이하이다. 모든 테스트 케이스의 $m$을 합하면 $2 \cdot 10^6$ 이하이다.

각 테스트 케이스마다 길이 $m$인 이진 문자열을 한 줄에 출력한다. $i$번째 자리는 $i$번째 질의의 답이 가능하면 '1', 불가능하면 '0'이다.