Read problems statements in Mandarin Chinese  and Russian. 
Chef has N simple polygons (non self intersecting polygons) in which no two of them intersect with each other. For any two polygons P_{1}, P_{2}, either P_{1} lies inside P_{2} or vice versa. 
Chef wants you to count number of polygons lying strictly inside each of the polygons.

------ Input ------ 

First line of the input contains an integer T denoting the number of test cases. First line of each test case contains a single integer N denoting the number of polygons.
The description of N polygons is as follows:

The first line contains an integer M_{i} denoting the number of vertices in the i^{th} polygon
The second line contains M_{i} pairs of integers X_{i, j}, Y_{i, j} representing coordinates of vertices of i^{th}  polygon in clockwise or counterclockwise order

------ Output ------ 

For each test case, output a single line containing N space-separated integers such that i^{th} of them represents number of polygons lying inside the i^{th} polygon.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
$3 ≤ M_{i} ≤ 10^{5}$
$The sum of M_{i} (or total amount of given points) over all test cases in one test file does not exceed 2*10^{5}$
$Absolute value of each coordinate doesn't exceed 10^{9}$

Subtask 1: (10 points)

$T ≤ 6$
$2 ≤ N ≤ 10$
$3 ≤ M_{i} ≤ 10$
$Absolute value of each coordinate doesn't exceed 30$

Subtask 2: (20 points)

$All polygons are  convex polygons .$

Subtask 3: (70 points)

$Original constraints$

----- Sample Input 1 ------ 
1
3
6
-2 2 -1 1 2 2 2 -1 1 -2 -2 -2
3
-1 -1 1 -1 1 1
4
3 3 -3 3 -3 -3 3 -3
----- Sample Output 1 ------ 
1 0 2
----- explanation 1 ------ 

In the picture the first polygon is marked in green, second - in red and third in blue color.

Difficulty: MEDIUM_HARD
Tags: Geometry

Sorting
Skill types: Sorting

Starter code:

Solutions:
from operator import itemgetter
import sys
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = []
	b = []
	d = {}
	l = [0] * n
	for i in range(n):
		m = int(input())
		c = list(map(int, input().split()))
		for j in range(2 * m):
			c[j] = abs(c[j])
		x = max(c[0:2 * m:2])
		y = max(c[1:2 * m:2])
		a.append(x)
		b.append(y)
	for i in range(n):
		d[i] = min(a[i], b[i])
	d = sorted(d.items(), key=itemgetter(1))
	for i in range(n):
		x = d[i][0]
		l[x] = i
	sys.stdout.write(' '.join((str(x) for x in l)))
	print()


import bisect

def solve():
	n = int(input())
	all = []
	for i in range(n):
		m = int(input())
		str = input().split()
		area = 0
		firstX = 0
		firstY = 0
		lastX = 0
		lastY = 0
		for j in range(0, 2 * m, 2):
			x = int(str[j])
			y = int(str[j + 1])
			if j == 0:
				firstX = x
				firstY = y
			else:
				area += lastX * y
				area -= lastY * x
			lastX = x
			lastY = y
		area += lastX * firstY
		area -= lastY * firstX
		all.insert(0, [abs(area), i])
	all.sort(key=lambda x: x[0])
	ans = [0] * n
	for i in range(n):
		ans[all[i][1]] = i
	for i in range(n):
		print('%d ' % ans[i], end='')
for tc in range(int(input())):
	solve()
	print('')


def coords_to_x_only(list_coordinates):
	x_list = list_coordinates[::2]
	return x_list

def find_rank_max_x(list_max, index):
	rank = 0
	for element in list_max:
		if element[1] == index:
			return rank
		else:
			rank += 1
cases = int(input())
for case in range(cases):
	nb_polygons = int(input())
	max_x_list = list()
	for polygon in range(nb_polygons):
		nb_vertices = int(input())
		coordinates = list(map(int, input().strip().split()))
		x_vertices = coords_to_x_only(coordinates)
		max_x_list.append((max(x_vertices), polygon))
	max_x_list_sorted = sorted(max_x_list)[::-1]
	nb_polygons_inside = [0] * nb_polygons
	for (max_x, index) in max_x_list_sorted:
		nb_polygons -= 1
		nb_polygons_inside[index] = str(nb_polygons)
	print(' '.join(nb_polygons_inside))


import sys
t = int(input())

def abs(x):
	if x > 0:
		return x
	return -x
while t:
	n = int(input())
	a = list()
	for i in range(n):
		m = int(input())
		line = input().split()
		pts = [(int(line[i]), int(line[i + 1])) for i in range(0, 2 * m, 2)]
		s = 0
		for j in range(m):
			k = (j + 1) % m
			if pts[k][0] - pts[j][0] > 0:
				s += (pts[j][0] - pts[k][0]) * (pts[k][1] + pts[j][1])
			else:
				s -= (pts[k][0] - pts[j][0]) * (pts[k][1] + pts[j][1])
		s /= 2
		s = abs(s)
		a.append((s, i))
	a.sort()
	ans = [0 for i in range(n)]
	for i in range(n):
		ans[a[i][1]] = i
	for x in ans:
		sys.stdout.write(str(x) + ' ')
	sys.stdout.write('\n')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = []
	ans = [0] * n
	for i in range(n):
		m = int(input())
		po = [int(i) for i in input().split()][::2]
		arr.append([i, max(po)])
	arr.sort(key=lambda x: x[1])
	for x in range(n):
		ans[arr[x][0]] = x
	print(*ans)


def polygonarea(xarr, yarr, m):
	area = xarr[0] * (yarr[1] - yarr[m - 1]) + xarr[m - 1] * (yarr[0] - yarr[m - 2])
	for i in range(1, m - 1):
		area = area + xarr[i] * (yarr[i + 1] - yarr[i - 1])
	return abs(area) / 2

def mysort(i):
	return area[i]
test = int(input())
for t in range(0, test):
	area = []
	n = int(input())
	rank = [0] * n
	for k in range(0, n):
		xarr = []
		yarr = []
		m = int(input())
		coords = input().split()
		for i in range(0, m):
			xarr.append(int(coords[2 * i]))
			yarr.append(int(coords[2 * i + 1]))
		area.append(polygonarea(xarr, yarr, m))
	index = list(range(0, n))
	index.sort(key=mysort)
	for k in range(0, n):
		rank[index[k]] = k
	for k in rank:
		print(k, end=' ')
	print('\n')


import sys

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def getX(self):
		return self.x

	def getY(self):
		return self.y

def Orientacion(p, q, r):
	return q.getx() * r.getY() + r.getX() * p.getY() + p.getX() * q.getY() - (q.getx() * p.getY() + r.getX() * q.getY() + p.getX() * r.getY())

def Graham(P):
	resp = []
	Lupper = []
	Llower = []
	n = len(P)
	sorted(P)
	i = 0
	while i < len(P):
		Lupper.append(P[i])
		k = len(Lupper)
		while k > 2 and Orientacion(Lupper[k - 3], Lupper[k - 2], Lupper[k - 1]) >= 0:
			del Lupper[k - 2]
			k -= 1
	i = len(P) - 1
	while i >= 0:
		Llower.append(P[i])
		k = len(Llower)
		while k > 2 and Orientacion(Llower[k - 3], Llower[k - 2], Llower[k - 1]) >= 0:
			del Llower[k - 2]
			k -= 1
	if len(Llower) > 0:
		del Llower[len(Llower) - 1]
	if len(Llower) > 0:
		del Llower[0]
	i = 0
	while i < len(Lupper):
		resp.append(Lupper[i])
	k = 0
	while k < len(Llower):
		resp.append(Llower[k])
	return resp
casos = int(input())
cont = 0
while cont < casos:
	n = int(input())
	i = 0
	polygons = []
	while i < n:
		points = int(input())
		line = input()
		array = line.split()
		array = list(map(int, array))
		j = 0
		pol = []
		while j < len(array):
			pol.append(tuple([array[j], array[j + 1]]))
			j += 2
		pol.sort()
		polygons.append(tuple([pol[0], i]))
		i += 1
	polygons.sort()
	answers = [0] * len(polygons)
	j = 0
	while j < len(polygons):
		answers[int(polygons[j][1])] = len(polygons) - j - 1
		j += 1
	answers = list(map(str, answers))
	line = ' '.join(answers)
	print(line)
	cont += 1


import operator
T = int(input())
for i in range(T):
	N = int(input())
	O = []
	P = {}
	L = {}
	for j in range(N):
		M = int(input())
		num = [int(n) for n in input().split()]
		maxDist = 0
		for k in range(0, 2 * M, 2):
			d = num[k] * num[k] + num[k + 1] * num[k + 1]
			if d > maxDist:
				maxDist = d
		P[j] = maxDist
	i = 0
	for j in sorted(P.items(), key=operator.itemgetter(1)):
		L[j] = i
		i += 1
	for j in sorted(L):
		print(L[j], end=' ')
	print()


a = int(input())
while a > 0:
	a -= 1
	b = int(input())
	P = {}
	P1 = {}
	l = 0
	while l < b:
		l += 1
		c = int(input())
		d1 = input()
		d = [int(n) for n in d1.split()]
		P[l] = min(d[0:][::2])
	s = sorted(P, key=P.__getitem__)
	for i in range(b):
		P1[s[i]] = b - 1 - i
	for i in P1.values():
		print(i, end=' ')


def run():
	T = int(input())
	for _ in range(T):
		N = int(input())
		polygons = []
		for i in range(N):
			M = int(input())
			polygon = list(map(int, input().split()))
			polygons.append(polygon)
		print(f(polygons))

def f(polygons):
	highest = []
	for (i, polygon) in enumerate(polygons):
		hi = float('-inf')
		for x in range(0, len(polygon), 2):
			(px, py) = (polygon[x], polygon[x + 1])
			hi = max(hi, py)
		highest.append((i, hi))
	highest = sorted(highest, key=lambda x: x[1])
	ans = [0] * len(polygons)
	for (n, (i, hi)) in enumerate(highest):
		ans[i] = str(n)
	return ' '.join(ans)
run()


t = int(input())
for it in range(t):
	n = int(input())
	x_pno_array = []
	for i in range(n):
		m = int(input())
		max_x_coord = max([int(word) for word in input().split()][::2])
		x_pno_array.append((max_x_coord, i))
	x_pno_array = sorted(x_pno_array)
	pno_rank_array = []
	for i in range(n):
		pno_rank_array.append((x_pno_array[i][1], i))
	pno_rank_array = sorted(pno_rank_array)
	print(*[elem[1] for elem in pno_rank_array])


t = int(input())
while t > 0:
	n = int(input())
	b = list(range(n))
	c = list(range(n))
	q = 0
	for i in range(0, n):
		m = int(input())
		a = list(map(int, input().split()))
		y = a[0]
		j = 2
		while j < len(a):
			temp = a[j]
			if y < temp:
				y = temp
			j = j + 2
		b[i] = y
		c[i] = b[i]
	c.sort()
	d = list(range(n))
	for i in range(0, n):
		first = 0
		last = len(c) - 1
		found = False
		while first <= last and (not found):
			midpoint = (first + last) // 2
			if c[midpoint] == b[i]:
				found = True
			elif b[i] < c[midpoint]:
				last = midpoint - 1
			else:
				first = midpoint + 1
		d[i] = midpoint
	print(' '.join(map(str, d)))
	t = t - 1


import sys
casos = int(input())
cont = 0
while cont < casos:
	n = int(input())
	i = 0
	polygons = []
	while i < n:
		points = int(input())
		line = input()
		array = line.split()
		array = list(map(int, array))
		j = 0
		pol = []
		while j < len(array):
			pol.append(tuple([array[j], array[j + 1]]))
			j += 2
		polygons.append(tuple([min(pol), i]))
		i += 1
	polygons.sort()
	answers = [0] * len(polygons)
	j = 0
	while j < len(polygons):
		answers[int(polygons[j][1])] = len(polygons) - j - 1
		j += 1
	answers = list(map(str, answers))
	line = ' '.join(answers)
	print(line)
	cont += 1


t = int(input())
for x in range(t):
	n = int(input())
	a = []
	for y in range(n):
		nod = int(input())
		lst = input().split()
		maxi = int(lst[0])
		k = 0
		while k < 2 * nod:
			maxi = max(maxi, int(lst[k]))
			k += 2
		a.append((maxi, y))
	b = sorted(a)
	c = []
	for z in range(n):
		c.append(0)
	h = 0
	for w in b:
		c[w[1]] = h
		h += 1
	s = ''
	for m in c:
		s = s + str(m) + ' '
	print(s)


from bisect import bisect_left as bl

def polygonArea(X, Y, n):
	area = 0.0
	j = n - 1
	for i in range(0, n):
		area += (X[j] + X[i]) * (Y[j] - Y[i])
		j = i
	return int(abs(area / 2.0))
for i in range(int(input())):
	area = []
	num_polygons = int(input())
	for i in range(num_polygons):
		vertices = int(input())
		pts = [int(x) for x in input().split()]
		(x, y) = ([], [])
		for j in range(2 * vertices):
			if j % 2:
				y.append(pts[j])
			else:
				x.append(pts[j])
		area.append(polygonArea(x, y, len(x)))
	area_copy = sorted(area)
	for i in area:
		print(bl(area_copy, i), end=' ')
	print()


import math

def brearch(lst, l, r, key):
	while l <= r:
		mid = int((l + r) / 2)
		if key == lst[mid]:
			return mid
		elif key < lst[mid]:
			r = mid - 1
		else:
			l = mid + 1
t = int(input())
it = 0
while it < t:
	n = int(input())
	area = []
	for i in range(n):
		m = int(input())
		a = []
		lst = list(map(int, input().split()))
		for k in range(0, len(lst), 2):
			a.append([lst[k], lst[k + 1]])
		a.append([a[0][0], a[0][1]])
		left = 0
		right = 0
		for j in range(m):
			left += a[j][0] * a[j + 1][1]
			right += a[j][1] * a[j + 1][0]
		area.append(math.fabs(left - right))
	ar = sorted(area)
	for i in range(n):
		print(brearch(ar, 0, n - 1, area[i]), end=' ')
	print()
	it += 1


for _ in range(int(input())):
	n = int(input())
	xs = []
	for i in range(n):
		m = int(input())
		xy = list(map(int, input().split()))
		x = xy[::2]
		xs.append((max(x), i))
	s = sorted(xs, reverse=True)
	answer = [None for i in range(n)]
	for i in range(len(s)):
		answer[s[i][1]] = str(n - 1 - i)
	print(' '.join(answer))


def getArea(listOfVertices, noOfVertices, times):
	randomStuff = noOfVertices * 2
	(sum1, sum2) = (0, 0)
	for i in range(noOfVertices):
		(x1, y1, x2, y2) = (listOfVertices[i * 2], listOfVertices[i * 2 + 1], listOfVertices[(i * 2 + 2) % randomStuff], listOfVertices[(i * 2 + 3) % randomStuff])
		(sum1, sum2) = (sum1 + x1 * y2, sum2 + x2 * y1)
	return [abs(sum1 / 2 - sum2 / 2), times]
tCase = int(input())
for eachCase in range(tCase):
	noOfPolygons = int(input())
	AreaList = []
	for times in range(noOfPolygons):
		noOfVertices = int(input())
		listOfVertices = [int(x) for x in input().split()]
		AreaList.append(getArea(listOfVertices, noOfVertices, times))
	AreaList.sort(key=lambda y: y[0])
	for index in range(noOfPolygons):
		AreaList[index].append(index)
	AreaList.sort(key=lambda y: y[1])
	for index in range(noOfPolygons):
		print(AreaList[index][2], end=' ')
	print()


__author__ = 'shreeshaprabhu'

def area(polygon):
	assert isinstance(polygon, list)
	a = 0
	n = len(polygon)
	for i in range(n):
		j = (i + 1) % n
		a += polygon[i][0] * polygon[j][1] - polygon[j][0] * polygon[i][1]
	return abs(a)

def solve():
	n = int(input())
	polygons = []
	for i in range(n):
		s = int(input())
		inp = input().split()
		polygon = [(int(inp[j * 2]), int(inp[j * 2 + 1])) for j in range(s)]
		polygons.append((i, area(polygon)))
	polygons.sort(key=lambda p: p[1])
	ans = [0 for _ in range(n)]
	for i in range(n):
		ans[polygons[i][0]] = i
	return ans
T = int(input())
for _ in range(T):
	print(*solve(), sep=' ', end='\n')


from operator import itemgetter
t = int(input())
for i in range(t):
	n = int(input())
	xseq = []
	for j in range(n):
		v = int(input())
		vert = list(map(int, input().split()))
		xseq.append([max(vert[::2]), j + 1, 0])
	xseq.sort(key=itemgetter(0))
	for j in range(n):
		xseq[j][2] = j
	xseq.sort(key=itemgetter(1))
	for j in range(n - 1):
		print(xseq[j][2], end=' ')
	print(xseq[n - 1][2])


for t in range(int(input())):
	n = int(input())
	a = []
	ans = []
	for p in range(n):
		ans.append(0)
		m = int(input())
		temp = list(map(int, input().split()))
		maxx = temp[0]
		i = 2
		while i < 2 * m:
			if temp[i] > maxx:
				maxx = temp[i]
			i += 2
		a.append([maxx, p])
	a.sort()
	for i in range(n):
		index = a[i][1]
		ans[index] = i
	for i in ans:
		print(i, end=' ')
	print()


def area(m, coords):
	r = 0
	j = m - 1
	for i in range(m):
		r += (coords[2 * i] + coords[2 * j]) * (coords[2 * j + 1] - coords[2 * i + 1])
		j = i
	return abs(r / 2)

def solve():
	for t in range(int(input())):
		areas = []
		n = int(input())
		for p in range(n):
			m = int(input())
			coords = [int(x) for x in input().split()]
			areas.append((area(m, coords), p))
		areas.sort(key=lambda x: x[0])
		res = [0] * n
		for i in range(n):
			res[areas[i][1]] = i
		for r in res:
			print(r, end=' ')
		print()
solve()


def area(l):
	prev = 0
	i = 2
	ans = 0
	while i < len(l):
		fr = l[prev] * l[i + 1]
		sec = l[prev + 1] * l[i]
		ans += fr - sec
		prev = i
		i += 2
	return abs(ans)
t = int(input())
for k in range(t):
	n = int(input())
	ar = []
	dic = {}
	for o in range(n):
		no = int(input())
		l = list(map(int, input().split()))
		l.append(l[0])
		l.append(l[1])
		x = area(l)
		dic[x] = o
		ar.append(x)
	new_ar = sorted(ar)
	ans = [0] * 100005
	for i in range(n):
		x = dic.get(new_ar[i])
		ans[x] = i
	for i in range(n):
		print(ans[i], end=' ')


t = int(input())
for i in range(t):
	n = int(input())
	ans = dict()
	res = dict()
	for k in range(n):
		m = int(input())
		x = input().split()
		mx_ar = 0
		for j in range(0, len(x), 2):
			d = int(x[j]) ** 2 + int(x[j + 1]) ** 2
			mx_ar = max(d, mx_ar)
		ans[mx_ar] = k
	k = 0
	for j in sorted(ans):
		res[ans[j]] = k
		k += 1
	for j in sorted(res):
		print(res[j], end=' ')
	print()