Outstanding Impressionist
Contest: Good Bye 2024: 2025 is NEAR
Difficulty rating: 1200
Tags: binary search, brute force, data structures, greedy

Even after copying the paintings from famous artists for ten years, unfortunately, Eric is still unable to become a skillful impressionist painter. He wants to forget something, but the white bear phenomenon just keeps hanging over him.

Eric still remembers $$$n$$$ pieces of impressions in the form of an integer array. He records them as $$$w_1, w_2, \ldots, w_n$$$. However, he has a poor memory of the impressions. For each $$$1 \leq i \leq n$$$, he can only remember that $$$l_i \leq w_i \leq r_i$$$.

Eric believes that impression $$$i$$$ is unique if and only if there exists a possible array $$$w_1, w_2, \ldots, w_n$$$ such that $$$w_i \neq w_j$$$ holds for all $$$1 \leq j \leq n$$$ with $$$j \neq i$$$.

Please help Eric determine whether impression $$$i$$$ is unique for every $$$1 \leq i \leq n$$$, independently for each $$$i$$$. Perhaps your judgment can help rewrite the final story.

Input format:
Each test contains multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) — the number of impressions.

Then $$$n$$$ lines follow, the $$$i$$$-th containing two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 2\cdot n$$$) — the minimum possible value and the maximum possible value of $$$w_i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output a binary string $$$s$$$ of length $$$n$$$: for each $$$1 \leq i \leq n$$$, if impression $$$i$$$ is unique, $$$s_i=\texttt{1}$$$; otherwise, $$$s_i=\texttt{0}$$$. Do not output spaces.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the only possible array $$$w$$$ is $$$[1, 1]$$$, making neither impression $$$1$$$ nor $$$2$$$ unique (since $$$w_1 = w_2$$$).

In the second test case, all impressions can be made unique:

- For $$$i = 1$$$, we can set $$$w$$$ to $$$[1, 3, 2, 3]$$$, in which $$$w_1 \neq w_2$$$, $$$w_1 \neq w_3$$$, and $$$w_1 \neq w_4$$$;
- For $$$i = 2$$$, we can set $$$w$$$ to $$$[2, 3, 1, 2]$$$, in which $$$w_2 \neq w_1$$$, $$$w_2 \neq w_3$$$, and $$$w_2 \neq w_4$$$;
- For $$$i = 3$$$, we can set $$$w$$$ to $$$[1, 1, 3, 1]$$$;
- For $$$i = 4$$$, we can set $$$w$$$ to $$$[2, 3, 3, 1]$$$.

In the third test case, for $$$i = 4$$$, we can set $$$w$$$ to $$$[3, 2, 2, 1, 3, 2]$$$. Thus, impression $$$4$$$ is unique.

Example input:
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

Example output:
00
1111
100110
1001111
011

Editorial:
For each $$$1 \leq i \leq n$$$, for each $$$l_i \leq x \leq r_i$$$, we want to check if it is okay for $$$w_i$$$ being unique at the value of $$$x$$$: for each $$$j \neq i$$$, we can always switch $$$w_j$$$ to a value different from $$$x$$$ if $$$l_j \neq r_j$$$; so if $$$l_j = r_j = x$$$ it's always invalid, otherwise it's okay.
Therefore, impression $$$i$$$ may contribute to a $$$\texttt{NO}$$$ only when it is fixed, that is, $$$l_i = r_i$$$.
Let's record $$$a_i$$$ as the number of different $$$k$$$ satisfying $$$1 \leq k \leq n$$$, $$$l_k = r_k = i$$$. If $$$l_i \neq r_i$$$, then we say impression $$$i$$$ cannot be made unique if and only if for all $$$l_i \leq k \leq r_i$$$, $$$a_k \geq 1$$$; and if $$$l_i = r_i$$$, it cannot be unique if and only if $$$a_{l_i} \geq 2$$$.
This can all be checked quickly within a prefix sum, so the overall time complexity is $$$\mathcal O(\sum n)$$$.