对于长度为 $$$n$$$ 的数组 $$$a$$$ 和三个整数 $$$x$$$、$$$l$$$ 和 $$$r$$$($$$1 \le l \le r \le n$$$),定义:
$$f(a,x,l,r) = \begin{cases} 0, & \text{if} & (x-\min_{j=l}^{r}(a_j)) \cdot (x-\max_{j=l}^{r}(a_j))) \lt 0 \\ 1, & \text{if} & (x-\min_{j=l}^{r}(a_j)) \cdot (x-\max_{j=l}^{r}(a_j))) \ge 0 \end{cases}$$
给定一个数组 $$$a$$$,长度为 $$$n$$$ ($$$1 \le a_i \le n$$$),间隔 $$$m$$$ $$$[l_i, r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$)。
对于每个 $$$x=1, 2, \dots, n$$$,回答以下问题 独立:
- 是否存在 $$$a$$$ 的重新排列 $$$a'$$$,使得对于 全部 $$$1 \le i \le m$$$, $$$f(a',x,l_i,r_i) = 1$$$?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。每个测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2000$$$, $$$1 \le m \le 2000$$$)。
下一行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le n$$$)。
接下来的 $$$m$$$ 行每行包含两个空格分隔的整数 $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$),每个表示一个区间。
保证所有测试用例的 $$$n^2$$$ 之和和 $$$m^2$$$ 之和分别不超过 $$$4 \cdot 10^6$$$。
输出
对于每个测试用例,输出一个二进制字符串$$$s$$$。对于 $$$x=1,2,\ldots,n$$$, $$$s_x=1$$$ 仅当存在 $$$a$$$ 的重新排列 $$$a'$$$ 时,这样对于 全部 $$$1 \le i \le m$$$,$$$f(a',x,l_i,r_i) = 1$$$。否则,$$$s_x=0$$$。
示例
输入复制
44 21 1 3 41 22 43 21 1 31 22 33 11 1 11 39 34 5 9 1 1 1 2 2 31 63 77 9
输出复制
1011101111100100001
注意
在第一个测试用例中,
- 对于 $$$x=1$$$,一个有效的重新排列是 $$$a'=[1,1,3,4]$$$。
- 对于 $$$x=2$$$,$$$a$$$ 不存在满足 $$$f(a',2,1,2)=f(a',2,2,4)=1$$$ 的重新排列 $$$a'$$$。
- 对于 $$$x=3$$$, 仅 仅有的 有效的重新排列为 $$$a'=[4,3,1,1]$$$。
- 对于 $$$x=4$$$,一个有效的重新排列是 $$$a'=[1,1,3,4]$$$。