You are given $n$ intervals on the $X$ axis. Each interval $i$ is specified by its ends $[L_i, R_i]$. You want to color each interval either blue or yellow. After coloring all the intervals, the $X$ axis will will have $4$ colors:
- White, the part of $X$ axis contained in no interval
- Blue, the part of $X$ axis contained in atleast one blue colored interval and no yellow colored interval.
- Yellow, the part of $X$ axis contained in atleast one yellow colored interval and no blue colored interval.
- Green, the part of $X$ axis contained in at least one blue colored interval and at least one yellow colored interval.
You want to color the intervals so that the total length of the part colored green is maximized. If there are multiple ways to color which maximize the green part, you can output any of them.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each testcase contains $n$, the number of intervals.
- The $i^{\text{th}}$ of the next $n$ lines contains two integers $L_i$ and $R_i$ describing the $i^{\text{th}}$ interval.

-----Output:-----
For each testcase, output a single string on a new line, whose $i^{\text{th}}$ character is $0$ if you color the $i^{\text{th}}$ interval blue, and $1$ if you color it yellow.

-----Constraints-----
- $ 1 \leq T \leq 10^5 $
- $ 1 \leq n \leq 10^5 $
- The sum of $n$ over all testcases doesn't exceed $10^5$.
- $ 1 \leq L_i \leq R_i \leq 10^9 $ for al $ 1 \leq i \leq n$.

-----Sample Input:-----
1
3
3 7
2 5
6 9

-----Sample Output:-----
100

-----Explanation:-----
The intervals are $[3, 7]$, $[2, 5]$, $[6, 9]$. It is optimal to color them in yellow, blue and blue respectively. In this coloring:
- $[2, 3) \cup (7, 9]$ is colored blue.
- $(5, 6)$ is colored yellow.
- $[3, 5] \cup [6, 7]$ is colored green, with a total length of $(5 - 3) + (7 - 6) = 3$.
- Rest of the $X$ axis is colored white.
Please note that colors at the endpoints of the intervals don't matter when computing the lengths, and we can ignore them. Open and closed intervals have been used in the explanation section only for clarity, and it doesn't matter whether they are open or closed.
Note that 011 is also a valid output.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 n = int(input())
 ls = []
 rs = []
 lrs = []

 for i in range(n):
  l, r = map(int, input().split())
  ls.append(l)
  rs.append(r)
  lrs.append((l, r, i))

 lrs.sort()

 c = 0
 maxi = -1

 res = [-1] * n
 for l, r, i in lrs:
  if ls[i] > maxi:
   maxi = rs[i]
   res[i] = c

  elif rs[i] <= maxi:
   res[i] = 1^c

  else:
   maxi = rs[i]
   c ^= 1
   res[i] = c

 print(*res, sep='')

for _ in range(int(input())):
 n = int(input())
 ls = []
 rs = []
 lrs = []

 for i in range(n):
  l, r = map(int, input().split())
  ls.append(l)
  rs.append(r)
  lrs.append((l, r, i))

 lrs.sort()

 c = 0
 maxi = -1

 res = [-1] * n
 for l, r, i in lrs:
  if ls[i] >= maxi:
   maxi = rs[i]
   res[i] = c

  elif rs[i] <= maxi:
   res[i] = 1^c

  else:
   maxi = rs[i]
   c ^= 1
   res[i] = c

 print(*res, sep='')

# cook your dish here
def f (arr: list):
 arr.sort()
 # print(arr)
 pl, pr, pc = float('-inf'), float('-inf'), 0
 col = [0 for x in range(len(arr))]
 for i in arr:
  nl, nr = i[0], i[1]
  if nl > pr:
   i.append(0)
   pl, pr, pc = nl, nr, 0
  else:
   nc = 0 if pc == 1 else 1
   i.append(nc)
   pc = nc if nr > pr else pc
   pr = max(pr, nr)
  col[i[2]] = str(i[3])
 return "".join(col)

T = int(input())
for t in range(T):
 n = int(input())
 arr = []
 for i in range(n):
  l, r = [int(x) for x in input().split()]
  arr.append([l,r,i])
 print(f(arr))

# cook your dish here
def f (arr: list):
 arr.sort()
 # print(arr)
 pl, pr, pc = float('-inf'), float('-inf'), 0
 col = [0 for x in range(len(arr))]
 for i in arr:
  nl, nr = i[0], i[1]
  if nl > pr:
   i.append(0)
   pl, pr, pc = nl, nr, 0
  else:
   nc = 0 if pc == 1 else 1
   i.append(nc)
   pc = nc if nr > pr else pc
   pr = max(pr, nr)
  col[i[2]] = str(i[3])
 return "".join(col)

T = int(input())
for t in range(T):
 n = int(input())
 arr = []
 for i in range(n):
  l, r = [int(x) for x in input().split()]
  arr.append([l,r,i])
 print(f(arr))