E. Правильная расстановка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп пригласил $$$n$$$ друзей на встречу Нового года. Во время торжества он решил сделать общую фотографию всех своих друзей. Каждый друг может стоять или лечь на бок.

Каждый друг характеризуется двумя значениями $$$h_i$$$ (его рост) и $$$w_i$$$ (его ширина). На фото $$$i$$$-й друг будет занимать прямоугольник $$$h_i \times w_i$$$ (если он стоит) или $$$w_i \times h_i$$$ (если он лежит).

Друга с номером $$$j$$$ можно разместить перед $$$i$$$-м другом на фотографии, если его прямоугольник ниже и уже, чем прямоугольник $$$i$$$-го друга. Формально должно быть выполнено хотя бы одно из следующих условий:

  • $$$h_j < h_i$$$ и $$$w_j < w_i$$$ (оба друга стоят или оба лежат);
  • $$$w_j < h_i$$$ и $$$h_j < w_i$$$ (один из друзей стоит, а другой лежит).

Например, если $$$n = 3$$$, $$$h=[3,5,3]$$$ и $$$w=[4,4,3]$$$, то:

  • первого друга можно поставить перед вторым: $$$w_1 < h_2$$$ и $$$h_1 < w_2$$$ (один из них стоит, а другой лежит);
  • третьего друга можно поставить перед вторым: $$$h_3 < h_2$$$ и $$$w_3 < w_2$$$ (оба друга стоят или оба лежат).

В других случаях человек на переднем плане будет перекрывать человека на заднем плане.

Помогите Поликарпу для каждого $$$i$$$ найти любой $$$j$$$, такой, что перед $$$i$$$-м другом может быть расположен $$$j$$$-й друг (т.е. хотя бы одно из условий выше было выполнено).

Обратите внимание, что вам не нужно находить расположение всех людей для общей фотографии. Вам нужно, чтобы каждый друг $$$i$$$ нашел любого другого друга $$$j$$$, который может оказаться перед ним. Думайте об этом, как о решении $$$n$$$ независимых подзадач.

Входные данные

В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора находится одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество друзей.

Далее следуют $$$n$$$ строк, каждая из которых содержит описание соответствующего друга. Каждый друг описывается двумя целыми числами $$$h_i$$$ и $$$w_i$$$ ($$$1 \leq h_i, w_i \leq 10^9$$$) — рост и ширина $$$i$$$-го друга, соответственно.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите $$$n$$$ целых чисел, где $$$i$$$-е число является номером друга, которого можно поставить перед $$$i$$$-м. Если такого друга не существует, то выведите -1.

Если существует несколько ответов, выведите любой.

Пример
Входные данные
4
3
3 4
5 4
3 3
3
1 3
2 2
3 1
4
2 2
3 1
6 3
5 4
4
2 2
2 3
1 1
4 4
Выходные данные
-1 3 -1 
-1 -1 -1 
-1 -1 2 2 
3 3 -1 3
Примечание

Первый набор входных данных разобран в условии.

Во третьем наборе входных данных следующие варианты ответы тоже являются верными:

  • $$$[-1, -1, 1, 2]$$$;
  • $$$[-1, -1, 1, 1]$$$;
  • $$$[-1, -1, 2, 1]$$$.