Scheduling

Your boss asked you to find a valid schedule for his meetings. He has $n$ meetings, and the $i$-th meeting must start and end within the time interval $[\ell_i, r_i]$, where time is measured in hours. Each meeting takes exactly one hour, and your boss cannot attend two meetings at the same time.

As a competitive programmer, you have solved this classic scheduling problem countless times, and only now do you notice that it is unrealistic. How can one person attend over a hundred thousand meetings in different places, with no travel time between them and no breaks at all? Meetings do not always last exactly one hour, and many start late because someone is running late.

These deep philosophical questions may be a big problem for humanity, but since you do not have to attend these meetings yourself, you do not care enough to solve all of them. Impressing your boss is worth it, though, so you try to improve the schedule at least a little.

Find any schedule where there is at least one hour between every pair of meetings, or report that there is none. This is just one small change to the classic problem, right?

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$), the number of test cases. The description of each test case follows.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), the number of meetings. The next $n$ lines each contain two integers $\ell_i$ and $r_i$ ($1 \leq \ell_i < r_i \leq 10^6$), the time interval of the $i$-th meeting.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

If there is no valid schedule, output $-1$ on a single line. Otherwise, output $n$ integers $a_i$ on a single line, where $a_i$ is the start time of the $i$-th meeting.

In the first test case, the first meeting starts at the start of hour $1$ and lasts one hour, until the start of hour $2$. After that, your boss takes a one-hour break before the third meeting, which runs from the start of hour $3$ to $4$. Then he takes another one-hour break before the second meeting, which runs from the start of hour $5$ to $6$.

Note that it is not possible to start the third meeting at the start of hour $4$, because that meeting would end at $5$.