The Siruseri Singing Championship is going to start, and Lavanya wants to figure out the outcome before the tournament even begins! Looking at past tournaments, she realizes that the judges care only about the pitches that the singers can sing in, and so she devises a method through which she can accurately predict the outcome of a match between any two singers. 
She represents various pitches as integers and has assigned a lower limit and an upper limit for each singer, which corresponds to their vocal range. For any singer, the lower limit will always be less than the upper limit. If a singer has lower limit $L$ and upper limit $U$ ($L < U$), it means that this particular singer can sing in all the pitches between $L$ and $U$, that is they can sing in the pitches {$L, L+1, L+2, \ldots, U$}. 
The lower bounds and upper bounds of all the singers are distinct. When two singers $S_i$ and $S_j$ with bounds ($L_i$, $U_i)$ and ($L_j$, $U_j$) compete against each other, $S_i$ wins if they can sing in every pitch that $S_j$ can sing in, and some more pitches. Similarly, $S_j$ wins if they can sing in every pitch that $S_i$ can sing in, and some more pitches. If neither of those two conditions are met, the match ends up as a draw. 
$N$ singers are competing in the tournament. Each singer competes in $N$-1 matches, one match against each of the other singers. The winner of a match scores 2 points, and the loser gets no points. But in case of a draw, both the singers get 1 point each.
You are given the lower and upper bounds of all the $N$ singers. You need to output the total scores of each of the $N$ singers at the end of the tournament.

-----Input-----
- The first line contains a single integer, $T$, which is the number of testcases. The description of each testcase follows.
- The first line of every testcase contains a single integer, $N$, which is the number of singers.
- $N$ lines follow, the i-th of which contains two integers: $L_i$ and $U_i$, which correspond to the lower bound and upper bound of the i-th singer.

-----Output-----
For each testcase output a single line containing $N$ integers, the i-th of which should be score of the i-th singer at the end of the tournament. 

-----Constraints-----
- $1 \le T \le 5$
- $2 \le N \le 10^5$
- $1 \le L_i < U_i \le 10^9$
- All the $2*N$ integers (lower bounds and upper bounds) are distinct.

-----Subtasks-----
Subtask #1 (15 points): $1 \le N \le 10^3$
Subtask #2 (25 points):
- $1 \le N \le 10^5$
- It is guaranteed that no match ends in a draw.
Subtask #3 (60 points): Original constraints.

-----Sample Input-----
2
3
10 20
13 18
15 19
3
10 22
13 21
15 20

-----Sample Output-----
4 1 1
4 2 0

-----Explanation-----
Testcase 1: There are three singers, with the lower bounds and upper bounds as (10, 20), (13, 18) and (15, 19).
When the first singer and second singer compete against each other in a match, we see that the second singer can sing in the pitches {13, 14, 15, 16, 17, 18}. Whereas the first singer can sing in the pitches {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}. So, we see that the first singer can sing everything that the second singer can, and also some other pitches. Hence the first singer wins this match, and gets 2 points. The second singer gets no points from this match.
When the first singer and third singer compete against each other in a match, we see that the third singer can sing in the pitches {15, 16, 17, 18, 19}. So again, we see that the first singer can sing everything that the third singer can. Hence the first singer wins this match, and gets 2 points. The third singer gets no points from this match.
When the second singer and third singer compete against each other in a match, we see that the second singer can sing in the pitches {13, 14, 15, 16, 17, 18}, whereas the third singer can sing in the pitches {15, 16, 17, 18, 19}. In particular, the second singer can sing in the pitch 14, which the third singer cannot sing in. And the third singer can sing in the pitch 19, which the second singer cannot sing in. So neither of the two conditions are met, and hence this match ends in a draw. Both the second and third singer get 1 point each.
Thus at the end of the tournament, the total score of first player is 2 + 2 = 4.
Total score of the second player is 0 + 1 = 1.
Total score of the third player is 0 + 1 = 1.
Hence the output is 4 1 1
Testcase 2: There are three singers, with the lower bounds and upper bounds as (10, 22), (13, 21) and (15, 20).
We see that the first singer wins against both second and third singers. And the second singer wins against the third singer. So the final total scores are (2 + 2), (0 + 2), (0 + 0), which is 4 2 0. Note that this would be a valid testcase in Subtask 2, because no match ends in a draw.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from operator import itemgetter
t = int(input())
for _ in range(t):
	n = int(input())
	start = []
	end = []
	for i in range(n):
		(first, last) = map(int, input().split())
		start.append((first, i))
		end.append((last, i))
	score = [0] * n
	start.sort(key=itemgetter(0))
	end.sort(key=itemgetter(0), reverse=True)
	for i in range(n - 1):
		score[start[i][1]] += n - i - 1
		score[end[i][1]] += n - i - 1
	print(' '.join([str(i) for i in score]))


def tourneyscore(a):
	scorelist = [0 for i in range(len(a))]
	for i in range(len(a)):
		for k in range(i + 1, len(a)):
			if a[i][0] < a[k][0]:
				if a[i][1] > a[k][1]:
					scorelist[i] += 2
				else:
					scorelist[i] += 1
					scorelist[k] += 1
			elif a[i][1] < a[k][1]:
				scorelist[k] += 2
			else:
				scorelist[i] += 1
				scorelist[k] += 1
	print(*scorelist, sep=' ')
for T in range(int(input())):
	singerlist = []
	for N in range(int(input())):
		(L, U) = input().split()
		(L, U) = (int(L), int(U))
		singerlist.append([L, U])
	tourneyscore(singerlist)


def tourneyscore(a):
	scorelist = []
	for i in range(len(a)):
		scorelist.append(0)
	for i in range(len(a)):
		for k in range(i + 1, len(a)):
			x = scorelist[i]
			y = scorelist[k]
			if a[i][0] < a[k][0] and a[i][1] > a[k][1]:
				scorelist[i] = x + 2
			elif a[i][0] > a[k][0] and a[i][1] < a[k][1]:
				scorelist[k] = y + 2
			else:
				scorelist[i] = x + 1
				scorelist[k] = y + 1
	for i in range(len(scorelist)):
		print(scorelist[i], end=' ')
	print()
for T in range(int(input())):
	singerlist = []
	for N in range(int(input())):
		(L, U) = input().split()
		(L, U) = (int(L), int(U))
		singerlist.append([L, U])
	tourneyscore(singerlist)


testcase = int(input(''))
for iterate in range(testcase):
	singers = int(input())
	lower_limit = []
	upper_limit = []
	for i in range(singers):
		(lower_limit_value, upper_limit_value) = map(int, input().split())
		lower_limit.append([lower_limit_value, i])
		upper_limit.append([upper_limit_value, i])
	lower_limit.sort(key=lambda x: x[0], reverse=True)
	upper_limit.sort(key=lambda x: x[0])
	score = [0] * singers
	for i in range(singers):
		score[upper_limit[i][1]] += i
		score[lower_limit[i][1]] += i
	print(*score)


for _ in range(int(input())):
	N = int(input())
	start = []
	end = []
	for i in range(N):
		(a, b) = list(map(int, input().split()))
		start.append([a, i])
		end.append([b, i])
	start.sort()
	end.sort()
	scores = [0] * N
	for i in range(N):
		p = start[i]
		q = end[i]
		scores[p[1]] += N - i - 1
		scores[q[1]] += i
	print(*scores)


try:
	t = int(input())
except:
	return
for q in range(t):
	n = int(input())
	score = [0] * n
	l = []
	u = []
	for q in range(n):
		(x, y) = map(int, input().split())
		l.append([x, q])
		u.append([y, q])
	l.sort(key=lambda x: x[0], reverse=True)
	u.sort(key=lambda x: x[0])
	for i in range(n):
		score[u[i][1]] += i
		score[l[i][1]] += i
	print(*score)


try:
	t = int(input())
except:
	return
for q in range(t):
	l = []
	n = int(input())
	score = [0] * n
	for w in range(n):
		li = list(map(int, input().split()))
		l.append(li)
	for x in range(n):
		for y in range(x + 1, n):
			if l[x][0] < l[y][0] and l[x][1] > l[y][1]:
				score[x] += 2
			elif l[y][0] < l[x][0] and l[y][1] > l[x][1]:
				score[y] += 2
			else:
				score[x] += 1
				score[y] += 1
	score = ''.join((str(e) + ' ' for e in score))
	print(score)


from itertools import combinations
T = int(input())
for case in range(T):
	n = int(input())
	scores = [0] * n
	pitch = []
	for i in range(n):
		(l, u) = map(int, input().split())
		pitch.append((l, u))
	for (i, j) in combinations(list(range(0, n)), 2):
		if pitch[i][0] < pitch[j][0] and pitch[i][1] > pitch[j][1]:
			scores[i] += 2
		elif pitch[i][0] > pitch[j][0] and pitch[i][1] < pitch[j][1]:
			scores[j] += 2
		else:
			scores[i] += 1
			scores[j] += 1
	print(' '.join((str(a) for a in scores)))


T = int(input())
for case in range(T):
	n = int(input())
	scores = [0] * n
	pitch = []
	for i in range(n):
		(l, u) = map(int, input().split())
		pitch.append((l, u))
	for i in range(n):
		for j in range(i + 1, n):
			if pitch[i][0] < pitch[j][0] and pitch[i][1] > pitch[j][1]:
				scores[i] += 2
			elif pitch[i][0] > pitch[j][0] and pitch[i][1] < pitch[j][1]:
				scores[j] += 2
			else:
				scores[i] += 1
				scores[j] += 1
	print(' '.join((str(a) for a in scores)))


def winner(x, y):
	if x[0] < y[0]:
		if x[1] >= y[1]:
			return 1
		else:
			return 0
	elif x[1] > y[1]:
		if x[0] <= y[0]:
			return 1
		else:
			return 0
	elif x[1] < y[1]:
		if x[0] >= y[0]:
			return 2
		else:
			return 0
	elif x[0] > y[0]:
		if x[1] <= y[1]:
			return 2
		else:
			return 0
	else:
		return 0
for _ in range(int(input())):
	n = int(input())
	part = []
	for _ in range(n):
		part.append(tuple(map(int, input().split())))
	score = [0] * n
	for i in range(n):
		x = part[i]
		if i < n - 1:
			new = part[i + 1:]
			for y in range(len(new)):
				if winner(x, new[y]) == 0:
					score[i] += 1
					score[i + y + 1] += 1
				elif winner(x, new[y]) == 1:
					score[i] += 2
				else:
					score[i + y + 1] += 2
	print(*score)


try:
	t = int(input())
except:
	return
for q in range(t):
	n = int(input())
	ans = [0] * n
	l = []
	for w in range(n):
		lu = list(map(int, input().split()))
		l.append(lu)
	for i in range(n):
		x = l[i]
		for j in range(i + 1, n):
			y = l[j]
			if x[0] < y[0] and x[1] > y[1]:
				ans[i] = ans[i] + 2
			elif y[0] < x[0] and y[1] > x[1]:
				ans[j] = ans[j] + 2
			else:
				ans[i] = ans[i] + 1
				ans[j] = ans[j] + 1
	s = ''.join((str(e) + ' ' for e in ans))
	print(s)


T = int(input())
for i in range(T):
	N = int(input())
	lower = []
	upper = []
	points = []
	for j in range(N):
		inputs = list(map(int, input().split()))
		lower.append(inputs[0])
		upper.append(inputs[1])
		points.append(0)
	for p in range(N):
		for m in range(p + 1, N):
			if lower[p] < lower[m] and upper[p] >= upper[m] or (lower[p] <= lower[m] and upper[p] > upper[m]):
				points[p] += 2
			elif lower[p] > lower[m] and upper[p] <= upper[m] or (lower[p] >= lower[m] and upper[p] < upper[m]):
				points[m] += 2
			else:
				points[p] += 1
				points[m] += 1
	for n in range(N):
		print(points[n], end=' ')
	print()


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
for _ in range(inp()):
	n = inp()
	sco = [0] * n
	(x, y) = ([], [])
	for i in range(n):
		(a, b) = ip()
		x.append([a, i])
		y.append([b, i])
	x.sort(reverse=True, key=lambda i: i[0])
	y.sort(key=lambda i: i[0])
	for i in range(n):
		sco[x[i][1]] += i
		sco[y[i][1]] += i
	print(*sco)


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
for _ in range(inp()):
	n = inp()
	tot = [0] * (n + 1)
	sco = [0] * n
	x = [ip() + [i] for i in range(n)]
	x.sort(key=lambda i: i[0])
	for i in range(n - 1):
		(l, r, i1) = (x[i][0], x[i][1], x[i][2])
		for j in reversed(list(range(i + 1, n))):
			(nl, nr, j1) = (x[j][0], x[j][1], x[j][2])
			if nl > l:
				if nr <= r:
					sco[i1] += 2
				else:
					sco[i1] += 1
					sco[j1] += 1
			elif nl == l:
				if nr > r:
					sco[j1] += 2
				elif nr == r:
					sco[i1] += 1
					sco[j1] += 1
				else:
					break
		if j > i + 1:
			sco[i1] += 2 * (j - i)
	print(*sco)


t = int(input())
for _ in range(t):
	n = int(input())
	lower = []
	upper = []
	for __ in range(n):
		(x, y) = map(int, input().split())
		lower.append([x, __])
		upper.append([y, __])
	lower.sort(key=lambda x: x[0], reverse=True)
	upper.sort(key=lambda x: x[0])
	dell = [0] * n
	for i in range(n):
		dell[upper[i][1]] += i
		dell[lower[i][1]] += i
	print(*dell)


t = int(input())
for _ in range(t):
	n = int(input())
	dell = []
	for __ in range(n):
		dell.append(list(map(int, input().split())))
	l = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			s1 = dell[i]
			s2 = dell[j]
			if s1[0] <= s2[0] and s1[1] > s2[1] or (s1[0] < s2[0] and s1[1] >= s2[1]):
				l[i][j] += 2
			elif s2[0] <= s1[0] and s2[1] > s1[1] or (s2[0] < s1[0] and s2[1] >= s1[1]):
				l[j][i] += 2
			else:
				l[i][j] += 1
				l[j][i] += 1
	for ele in l:
		print(sum(ele), end=' ')
	print()