由于北极的供应链问题(据称是由懒惰的小精灵造成),圣诞老人计划在今年圣诞节分发手绘圆圈作为礼物。请帮他装饰它们!
圆周围有 $$$2n$$$ 等距点,按顺时针顺序标记为 $$$1,2,\ldots,2n$$$。圣诞老人选择了 $$$n$$$ 和弦 不同 上面写着 端点,其中弦 $$$i$$$ 连接点 $$$a_i$$$ 和 $$$b_i$$$。他将这些和弦按顺序一一画在圆圈上。
圣诞老人画完第一个 $$$\ell$$$ 和弦后,考虑 $$$\ell$$$ 和弦的任何非空子集 $$$S$$$ 并让 $$$1\leq c_1 \lt c_2 \lt \cdots \lt c_{|S|}\leq \ell$$$ 为其索引。 $$$S$$$ 被定义为 链条 当且仅当和弦 $$$c_k$$$ 与所有 $$$1\leq k \lt |S|$$$ 与和弦 $$$c_{k+1}$$$ 相交。请注意,$$$S$$$ 始终是 链条 如果$$$|S|=1$$$。
圣诞老人不希望任何和弦出现异常。因此,他认为和弦是 紧密结合 当且仅当每个和弦出现在偶数个中 链条,接管全部 链条 是第一个 $$$\ell$$$ 和弦的子集。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$\ell$$$,帮助圣诞老人确定他的和弦是否 紧密结合.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 和弦是,则第 $$$\ell$$$ 个字符应该是 $$$\texttt{1}$$$ 紧密结合 和 $$$\texttt{0}$$$ 否则。
示例
输入复制
331 62 34 541 73 84 62 551 64 92 75 103 8
输出复制
000010001111
注意
在第一个测试用例中,没有成对的和弦相交,因此每个和弦都恰好出现在一个 链条 由其自身组成。因此,和弦不是 紧密结合 对于所有$$$\ell$$$。
在第二个测试用例中,下面是绘制第一个 $$$\ell=1,2,3,4$$$ 和弦后的说明和解释。和弦组被表示为一组对应和弦的索引。
| 插图 | |
链条
| ![]() |
链条
| ![]() |
链条
| ![]() |
链条
| ![]() |
因此,我们输出$$$\mathtt{0100}$$$。



