H. Beautiful Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For an array $$$a$$$ of length $$$n$$$ and three integers $$$x$$$, $$$l$$$, and $$$r$$$（$$$1 \le l \le r \le n$$$), define:

$$$$$$ 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} $$$$$$

You are given an array $$$a$$$ of length $$$n$$$ ($$$1 \le a_i \le n$$$), and $$$m$$$ intervals $$$[l_i, r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$).

For each $$$x=1, 2, \dots, n$$$, answer the following question independently:

  • Does there exist a rearrangement $$$a'$$$ of $$$a$$$, such that for all $$$1 \le i \le m$$$, $$$f(a',x,l_i,r_i) = 1$$$?
Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Description of each testcase follows.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2000$$$, $$$1 \le m \le 2000$$$).

The next line contains $$$n$$$ space-separated integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le n$$$).

The next $$$m$$$ lines each contain two space-separated integers $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$), each denoting an interval.

It is guaranteed that the sum of $$$n^2$$$ and the sum of $$$m^2$$$ over all test cases does not exceed $$$4 \cdot 10^6$$$, respectively.

Output

For each test case, output a binary string $$$s$$$. For $$$x=1,2,\ldots,n$$$, $$$s_x=1$$$ only if there exists a rearrangement $$$a'$$$ of $$$a$$$, such that for all $$$1 \le i \le m$$$, $$$f(a',x,l_i,r_i) = 1$$$. Otherwise, $$$s_x=0$$$.

Example
Input
4
4 2
1 1 3 4
1 2
2 4
3 2
1 1 3
1 2
2 3
3 1
1 1 1
1 3
9 3
4 5 9 1 1 1 2 2 3
1 6
3 7
7 9
Output
1011
101
111
100100001
Note

In the first test case,

  • For $$$x=1$$$, one valid rearrangement is $$$a'=[1,1,3,4]$$$.
  • For $$$x=2$$$, there is no rearrangement $$$a'$$$ of $$$a$$$ satisfying $$$f(a',2,1,2)=f(a',2,2,4)=1$$$.
  • For $$$x=3$$$, the only valid rearrangement is $$$a'=[4,3,1,1]$$$.
  • For $$$x=4$$$, one valid rearrangement is $$$a'=[1,1,3,4]$$$.