In the city NN, the construction of a mafia cafe has been completed. The tables in this cafe are single-seaters and numbered from $$$1$$$ to $$$n$$$ in order of attractiveness, where table $$$1$$$ is the most attractive, and table $$$n$$$ is the least attractive. For convenience, we will also number the mafia members from $$$1$$$ to $$$n$$$ in order of their significance, so that number $$$1$$$ is the most significant mafia boss, and number $$$n$$$ is the least significant recruit.
Mafiosi are very busy people; the $$$i$$$-th of them has only one slot in their schedule when they can visit the cafe — from time $$$a_i$$$ to time $$$b_i$$$ inclusively, and they want to spend all that time in the cafe.
The cafe administrator plans to seat people at the tables, trying to assign the most attractive tables to the most significant mafia members. Mafioso number $$$1$$$ will be seated at table number $$$1$$$, thus occupying that table from time $$$a_1$$$ to time $$$b_1$$$ inclusively. The administrator will also try to seat mafioso number $$$2$$$ at table number $$$1$$$, but if the segments $$$[a_1, b_1]$$$ and $$$[a_2, b_2]$$$ overlap, this will not be possible, and mafioso number $$$2$$$ will get table number $$$2$$$. Each mafioso number $$$i$$$ will be seated at the lowest numbered table that is free during the time segment from $$$a_i$$$ to $$$b_i$$$. Both boundaries of the segment are included, i.e., if for some mafiosi $$$i$$$ and $$$j$$$ it holds that $$$b_i = a_j$$$, they must be assigned different tables.
Help the administrator to arrange the seating.
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.
In the first line of each test case, there is an integer number $$$n$$$ ($$$1 \le n \le 250\,000$$$) — the number of mafiosi and tables.
In the $$$i$$$-th of the following $$$n$$$ lines, there are two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i \le b_i \le 2n$$$), meaning that the $$$i$$$-th mafioso plans to be in the cafe during the time from $$$a_i$$$ to $$$b_i$$$, inclusively.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$250\,000$$$.
For each test case, output $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$, where $$$c_i$$$ is the number of the table that the $$$i$$$-th mafioso will sit at.
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