H. Beautiful Problemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputFor 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))) < 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$$$? InputThe 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.OutputFor 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$$$.ExampleInput44 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 9Output1011101111100100001NoteIn 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]$$$.