H. Красивая задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$a$$$ длины $$$n$$$ и трех целых чисел $$$x$$$, $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$), определим:

$$$$$$ f(a,x,l,r) = \begin{cases} 0, & \text{если} & (x-\min_{j=l}^{r}(a_j)) \cdot (x-\max_{j=l}^{r}(a_j))) \lt 0 \\ 1, & \text{если} & (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$$$.

Пример
Входные данные
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
Выходные данные
1011
101
111
100100001
Примечание

В первом наборе данных,

  • Для $$$x=1$$$, одна допустимая перестановка это $$$a'=[1,1,3,4]$$$.
  • Для $$$x=2$$$, нет перестановки $$$a'$$$ массива $$$a$$$, удовлетворяющей $$$f(a',2,1,2)=f(a',2,2,4)=1$$$.
  • Для $$$x=3$$$, единственная допустимая перестановка это $$$a'=[4,3,1,1]$$$.
  • Для $$$x=4$$$, одна допустимая перестановка это $$$a'=[1,1,3,4]$$$.