В городе NN закончилось строительство кафе для мафии. Столики в этом кафе одноместные и пронумерованы числами от $$$1$$$ до $$$n$$$ в порядке привлекательности, где столик $$$1$$$ является самым привлекательным, а столик $$$n$$$ — самым непривлекательным. Для удобства также пронумеруем членов мафии числами от $$$1$$$ до $$$n$$$ в порядке их значимости, так что номер $$$1$$$ — это самый значимый босс мафии, а номер $$$n$$$ — самый незначительный новобранец.
Мафиози — очень занятые люди, и у $$$i$$$-го из них есть лишь один временной промежуток в расписании, когда он может посетить кафе — с момента времени $$$a_i$$$ до момента времени $$$b_i$$$ включительно, и он хочет провести в кафе всё это время.
Администратор кафе планирует рассадку людей за столики, стараясь самым значимым членам мафии отдать самые привлекательные столики. Мафиози номер $$$1$$$ он посадит за стол номер $$$1$$$, тем самым заняв этот стол в промежуток времени с $$$a_1$$$ до $$$b_1$$$. Мафиози номер $$$2$$$ он попробует также посадить за стол номер $$$1$$$, но если отрезки $$$[a_1, b_1]$$$ и $$$[a_2, b_2]$$$ пересекаются, то сделать это не получится, и мафиози номер $$$2$$$ достанется стол номер $$$2$$$.
Таким образом, мафиози номер $$$i$$$ назначают столик сразу после мафиози номер $$$i-1$$$. Из всех свободных (в промежуток времени с $$$a_i$$$ до $$$b_i$$$) столиков мафиози номер $$$i$$$ посадят за столик с наименьшим номером. Обратите внимание, что обе границы отрезка включены в него, то есть, если для каких-то двух различных мафиози $$$i$$$ и $$$j$$$ верно, что $$$b_i = a_j$$$, то им обязательно должны достаться разные столики.
Помогите администратору составить рассадку.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 250\,000$$$) — число мафиози и столиков соответственно.
Далее в наборе входных данных следует $$$n$$$ строк, $$$i$$$-я из них содержит два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i \le b_i \le 2n$$$), означающих, что $$$i$$$-й мафиози планирует быть в кафе в период времени с $$$a_i$$$ по $$$b_i$$$ включительно.
Гарантируется, что сумма $$$n$$$ по всем тестовым наборам не превосходят $$$250\,000$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$, где $$$c_i$$$ — это номер столика, за который сядет $$$i$$$-й мафиози.
531 11 22 341 13 31 22 323 41 242 32 52 44 531 11 22 3
1 2 11 1 2 31 11 2 3 11 2 1