如果一个非空字符串 $s$ 仅由字符 ‘0’ 和 ‘1’ 组成，则称其为二进制字符串。字符串 $s = s_1s_2 \dots s_{|s|}$（其中 $|s|$ 为字符串 $s$ 的长度）的子串 $s[l \dots r]$ ($1 \le l \le r \le |s|$) 是指字符串 $s_l s_{l+1} \dots s_r$。

张教授有一个以 ‘0’ 开头的长二进制字符串 $s$，他想知道是否存在一个 $s$ 的子串，使得该子串中 ‘0’ 和 ‘1’ 的出现次数恰好分别为给定的两个整数 $a$ 和 $b$。

由于该二进制字符串非常长，我们将对其进行压缩。压缩方法如下： 将字符串拆分为若干个由相同连续字符组成的游程（run）。 任意两个相邻的游程由不同的字符组成。使用每个游程的长度来表示该字符串。

例如，二进制字符串 “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$)：游程的数量和询问的数量。下一行包含 $n$ 个整数：$x_1, x_2, \dots, 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|$)，表示张教授想知道是否存在一个 $s$ 的子串，使得该子串中 ‘0’ 和 ‘1’ 的出现次数恰好分别为 $a_i$ 和 $b_i$。

测试数据不超过 200 组，输入总大小不超过 20 mebibytes。此外，所有测试数据中 $m$ 的总和不超过 $2 \cdot 10^6$。

输出格式

对于每组测试数据，输出一个长度为 $m$ 的二进制字符串。如果第 $i$ 个询问的答案为“是”，则第 $i$ 位必须为 ‘1’，否则为 ‘0’。

样例

输入 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