|
Пусть имеется N невырожденных прямоугольников со сторонами, параллельными координатным осям. Известно, что границы этих прямоугольников не пересекаются и одинаковых границ нет.
Будем говорить, что прямоугольник A вложен внутрь прямоугольника B, если любая точка, принадлежащая A, также принадлежит B, и A B.
Будем говорить, что прямоугольник A непосредственно вложен внутрь прямоугольника B, если A вложен в B, и A не вложен в любой другой прямоугольник, вложенный в B.
Напишите программу для анализа непосредственного вложения прямоугольников.
Ограничения
1 <= N <= 100 000;
0 <= x, y
< 231 – координаты противоположных вершин прямоугольника.
Входные данные
Первая строка входного файла содержит целое число N . Затем следуют N строк. Из них строка с номером i содержит 4 целых числа:
xi1, yi1,
xi2, yi2 — координаты противоположных вершин i -го прямоугольника.
Выходные данные
Запишите N строк в выходной файл. Номер строки i должен содержать номер прямоугольника, внутри которого непосредственно вложен прямоугольник с номером i , или 0, если во входном наборе такого прямоугольника нет.
Пример
|
Standard input
|
Standard output
|
|
5
0 0 10
10
1 2 4 5
2 3 3 4
7 7 8 8
0 11 1
12
|
0
1
2
1
0
|
| 
