G. Хорда или украшение
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Из-за проблем с цепочкой поставок на Северном полюсе (предположительно, вызванных ленивым эльфом) Санта планирует дарить нарисованные от руки круги в качестве подарков на это Рождество. Пожалуйста, помогите ему украсить их!

Вокруг круга расположены $$$2n$$$ равномерно распределенных точек, пронумерованных $$$1,2,\ldots,2n$$$ по часовой стрелке. Санта выбрал $$$n$$$ хорд с различными конечными точками, где хорда $$$i$$$ соединяет точки $$$a_i$$$ и $$$b_i$$$. Он рисует эти хорды на круге одну за другой по порядку.

После того как Санта нарисует первые $$$\ell$$$ хорд, рассмотрим любое непустое подмножество $$$S$$$ из $$$\ell$$$ хорд и пусть $$$1\leq c_1 \lt c_2 \lt \cdots \lt c_{|S|}\leq \ell$$$ будут их индексы. $$$S$$$ определяется как цепочка, если и только если хорда $$$c_k$$$ пересекает хорду $$$c_{k+1}$$$ для всех $$$1\leq k \lt |S|$$$. Обратите внимание, что $$$S$$$ всегда является цепочкой, если $$$|S|=1$$$.

Санта не хочет, чтобы какая-либо хорда была лишней. Поэтому он считает, что хорды являются плотно связанными, если и только если каждая хорда появляется в четном количестве цепочек, среди всех цепочек, которые являются подмножествами первых $$$\ell$$$ хорд.

Для каждого $$$\ell$$$ от $$$1$$$ до $$$n$$$ помогите Санте определить, являются ли его хорды плотно связанными.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\le n\le 5\cdot 10^5$$$) — количество хорд.

Затем следуют $$$n$$$ строк, в $$$i$$$-й строке содержатся два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1\le a_i \lt b_i\le 2n$$$) — конечные точки $$$i$$$-й хорды.

Гарантируется, что все конечные точки различны.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите строку длиной $$$n$$$ — $$$\ell$$$-й символ должен быть $$$\texttt{1}$$$, если первые $$$\ell$$$ хорд являются плотно связанными, и $$$\texttt{0}$$$ в противном случае.

Пример
Входные данные
3
3
1 6
2 3
4 5
4
1 7
3 8
4 6
2 5
5
1 6
4 9
2 7
5 10
3 8
Выходные данные
000
0100
01111
Примечание

В первом наборе входных данных ни одна пара хорд не пересекается, и, следовательно, каждая хорда появляется ровно в одной цепочке, состоящей из самой себя. Поэтому хорды не являются плотно связанными для всех $$$\ell$$$.

Во втором наборе входных данных ниже приведена иллюстрация и объяснение после того, как нарисованы первые $$$\ell=1,2,3,4$$$ хорды. Наборы хорд обозначены как набор индексов соответствующих хорд.

Объяснение
Иллюстрация
Цепочки
  • $$$\{1\}$$$.
Появления
  • Хорда $$$1$$$ появляется в $$$1$$$ цепочке.
Примечания
  • Хорды не являются плотно связанными, поскольку хорда $$$1$$$ находится в нечетном количестве цепочек.
  • Напоминаем, что набор, содержащий одну хорду, всегда является цепочкой.
Цепочки
  • $$$\{1\}$$$, $$$\{1,2\}$$$ и $$$\{2\}$$$.
Появления
  • Хорда $$$1$$$ появляется в $$$2$$$ цепочках;
  • Хорда $$$2$$$ появляется в $$$2$$$ цепочках.
Примечания
  • Хорды являются плотно связанными, поскольку каждая хорда появляется в четном количестве цепочек.
Цепочки
  • $$$\{1\}$$$, $$$\{1,2\}$$$, $$$\{2\}$$$ и $$$\{3\}$$$.
Появления
  • Хорда $$$1$$$ появляется в $$$2$$$ цепочках;
  • Хорда $$$2$$$ появляется в $$$2$$$ цепочках;
  • Хорда $$$3$$$ появляется в $$$1$$$ цепочке.
Примечания
  • Хорды не являются плотно связанными, поскольку хорда $$$3$$$ находится в нечетном количестве цепочек.
Цепочки
  • $$$\{1\}$$$, $$$\{1,2\}$$$, $$$\{1,2,4\}$$$, $$$\{2\}$$$, $$$\{2,4\}$$$, $$$\{3\}$$$, $$$\{3,4\}$$$ и $$$\{4\}$$$.
Появления
  • Хорда $$$1$$$ появляется в $$$3$$$ цепочках;
  • Хорда $$$2$$$ появляется в $$$4$$$ цепочках;
  • Хорда $$$3$$$ появляется в $$$2$$$ цепочках;
  • Хорда $$$4$$$ появляется в $$$4$$$ цепочках.
Примечания
  • Хорды не являются плотно связанными, поскольку хорда $$$1$$$ находится в нечетном количестве цепочек.
  • Обратите внимание, что $$$\{2,3,4\}$$$ не является цепочкой, поскольку хорда $$$2$$$ не пересекает хорду $$$3$$$.

Таким образом, мы выводим $$$\mathtt{0100}$$$.