CF920B.Tea Queue

Recently n students from city S moved to city P to attend a programming camp.

They moved there by train. In the evening, all students in the train decided that they want to drink some tea. Of course, no two people can use the same teapot simultaneously, so the students had to form a queue to get their tea.

i-th student comes to the end of the queue at the beginning of l__i-th second. If there are multiple students coming to the queue in the same moment, then the student with greater index comes after the student with lesser index. Students in the queue behave as follows: if there is nobody in the queue before the student, then he uses the teapot for exactly one second and leaves the queue with his tea; otherwise the student waits for the people before him to get their tea. If at the beginning of r__i-th second student i still cannot get his tea (there is someone before him in the queue), then he leaves the queue without getting any tea.

For each student determine the second he will use the teapot and get his tea (if he actually gets it).

最近，有 $n$ 名来自城市 S 的学生前往城市 P 参加编程训练营。

他们乘坐火车抵达。当晚，火车上的所有学生决定想喝些茶。当然，同一时刻不能有两人共用同一个茶壶，因此学生们必须排成一队依次取茶。

第 $i$ 名学生在第 $l_i$ 秒初到达队尾。若多名学生在同一时刻到达队尾，则编号较大的学生排在编号较小的学生之后。队列中的学生行为如下：若该学生前面无人，则他立即使用茶壶恰好 1 秒，随后带着茶离开队列；否则，该学生需等待其前方所有学生取完茶。若在第 $r_i$ 秒初，第 $i$ 名学生仍未能取到茶（即其前方仍有学生未完成取茶），则他将直接离开队列，不获得任何茶。

对每名学生，请确定其使用茶壶并取到茶的具体秒数（若他确实成功取到了茶）。

The first line contains one integer t — the number of test cases to solve (1 ≤ t ≤ 1000).

Then t test cases follow. The first line of each test case contains one integer n (1 ≤ n ≤ 1000) — the number of students.

Then n lines follow. Each line contains two integer l__i, r__i (1 ≤ l__i ≤ r__i ≤ 5000) — the second i-th student comes to the end of the queue, and the second he leaves the queue if he still cannot get his tea.

It is guaranteed that for every condition l__i - 1 ≤ l__i holds.

The sum of n over all test cases doesn't exceed 1000.

Note that in hacks you have to set t = 1.

第一行包含一个整数 $t$ —— 需要解决的测试用例数量（$1 \leq t \leq 1000$）。

接下来是 $t$ 个测试用例。每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 1000$）—— 学生人数。

接下来是 $n$ 行，每行包含两个整数 $l_i$、$r_i$（$1 \leq l_i \leq r_i \leq 5000$）—— 第 $i$ 个学生在第 $l_i$ 秒到达队尾，并在第 $r_i$ 秒离开队列（若此时仍未拿到茶）。

保证对每个 ，均有 $l_{i-1} \leq l_i$ 成立。

所有测试用例中 $n$ 的总和不超过 $1000$。

注意：在 hack 中，你必须设置 $t = 1$。

For each test case print n integers. i-th of them must be equal to the second when i-th student gets his tea, or 0 if he leaves without tea.

对每个测试用例，输出 $n$ 个整数。其中第 $i$ 个整数必须等于第 $i$ 位学生拿到茶水的时刻（单位：秒），如果该学生未领到茶水就离开了，则输出 0。

The example contains 2 tests:

1. During 1-st second, students 1 and 2 come to the queue, and student 1 gets his tea. Student 2 gets his tea during 2-nd second.
2. During 1-st second, students 1 and 2 come to the queue, student 1 gets his tea, and student 2 leaves without tea. During 2-nd second, student 3 comes and gets his tea.

该示例包含 2 个测试用例：

1. 在第 1 秒，学生 1 和学生 2 进入队列，学生 1 领取了茶；学生 2 在第 2 秒领取了茶。
2. 在第 1 秒，学生 1 和学生 2 进入队列，学生 1 领取了茶，而学生 2 未领到茶便离开了；在第 2 秒，学生 3 到达并领取了茶。