不幸的是,即使在临摹名家画作十年之后,艾瑞克仍然无法成为一名熟练的印象派画家。他想要忘记一些事情,但白熊现象却一直笼罩着他。
Eric 仍然记得整数数组形式的 $$$n$$$ 次展示。他将它们记录为 $$$w_1, w_2, \ldots, w_n$$$。然而,他对印象的记忆力很差。对于每个$$$1 \leq i \leq n$$$,他只能记住$$$l_i \leq w_i \leq r_i$$$。
Eric 认为印象 $$$i$$$ 是唯一的,当且仅当存在一个可能的数组 $$$w_1, w_2, \ldots, w_n$$$ 使得 $$$w_i \neq w_j$$$ 对于所有 $$$1 \leq j \leq n$$$ 和 $$$j \neq i$$$ 成立。
请帮助 Eric 确定印象 $$$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$$$。
输出
对于每个测试用例,输出长度为 $$$n$$$ 的二进制字符串 $$$s$$$:对于每个 $$$1 \leq i \leq n$$$,如果印象 $$$i$$$ 是唯一的,则 $$$s_i=\texttt{1}$$$;否则,$$$s_i=\texttt{0}$$$。不要输出空格。
示例
输入 #1
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
输出 #1
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$$$ 是独一无二的。