B. Выдающийся импрессионист
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
If it was so, then let's make it a deal...
— MayDay, Gentleness

К сожалению, даже после десяти лет копирования картин известных художников, Эрик все еще не смог стать искусным художником-импрессионистом. Он хочет что-то забыть, но феномен белого медведя продолжает нависать над ним.

Эрик до сих пор помнит $$$n$$$ впечатлений в виде целочисленного массива. Он записал их как $$$w_1, w_2, \ldots, w_n$$$. Однако у него плохая память на впечатления. Для каждого $$$1 \leq i \leq n$$$ он только запомнил, что выполнялось условие $$$l_i \leq w_i \leq r_i$$$.

Эрик считает, что впечатление $$$i$$$ является уникальным тогда и только тогда, когда существует массив $$$w_1, w_2, \ldots, w_n$$$, в котором $$$w_i \neq w_j$$$ выполняется для всех $$$1 \leq j \leq n$$$, где $$$j \neq i$$$.

Пожалуйста, помогите Эрику определить, является ли впечатление $$$i$$$ уникальным для каждого $$$1 \leq i \leq n$$$, независимо для каждого $$$i$$$. Возможно, ваше суждение поможет переписать финальную историю.

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

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

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

Далее следует $$$n$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 2\cdot n$$$) — минимально возможное значение и максимально возможное значение для $$$w_i$$$.

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

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

Для каждого набора входных данных выведите бинарную строку $$$s$$$ длины $$$n$$$: для каждого $$$1 \leq i \leq n$$$, если впечатление $$$i$$$ уникально, то $$$s_i=\texttt{1}$$$; в противном случае, $$$s_i=\texttt{0}$$$. Выводите строку без пробелов.

Пример
Входные данные
5
2
1 1
1 1
4
1 3
1 3
1 3
1 3
6
3 6
2 2
1 2
1 1
3 4
2 2
7
3 4
4 4
4 4
1 3
2 5
1 4
2 2
3
4 5
4 4
5 5
Выходные данные
00
1111
100110
1001111
011
Примечание

В первом наборе входных данных единственным возможным массивом $$$w$$$ является $$$[1, 1]$$$, в котором ни $$$1$$$, ни $$$2$$$ впечатления не являются уникальными (поскольку $$$w_1 = w_2$$$).

Во втором наборе входных данных все впечатления могут быть уникальными:

  • Для $$$i = 1$$$ мы можем сделать $$$w$$$ равным $$$[1, 3, 2, 3]$$$, и в нём $$$w_1 \neq w_2$$$, $$$w_1 \neq w_3$$$ и $$$w_1 \neq w_4$$$;
  • Для $$$i = 2$$$ мы можем сделать $$$w$$$ равным $$$[2, 3, 1, 2]$$$, и в нём $$$w_2 \neq w_1$$$, $$$w_2 \neq w_3$$$ и $$$w_2 \neq w_4$$$;
  • Для $$$i = 3$$$ мы можем сделать $$$w$$$ равным $$$[1, 1, 3, 1]$$$;
  • Для $$$i = 4$$$ мы можем сделать $$$w$$$ равным $$$[2, 3, 3, 1]$$$.

В третьем наборе входных данных, для $$$i = 4$$$ мы можем сделать $$$w$$$ равным $$$[3, 2, 2, 1, 3, 2]$$$. Таким образом, впечатление $$$4$$$ — уникально.