最近S市的n名学生搬到P市参加编程营。
他们乘火车搬到那里。晚上,火车上的所有学生都决定要喝点茶。当然,没有两个人可以同时使用同一个茶壶,所以学生们必须排着队去拿茶。
第 i 个学生在第 li 秒开始时到达队列末尾。如果同一时刻有多个学生进入队列,则索引较大的学生排在索引较小的学生之后。队列中的学生的行为如下:如果队列中没有人在该学生之前,则他使用茶壶正好一秒钟,然后带着茶离开队列;否则,学生会等待他前面的人去拿茶。如果在第二个学生开始时我仍然无法得到他的茶(队列中有人在他前面),那么他就离开队列而没有得到任何茶。
对于每个学生,确定他将使用茶壶并取茶的第二秒(如果他确实得到了茶)。
输入
第一行包含一个整数 t — 要解决的测试用例数量 (1 ≤ t ≤ 1000)。
然后是测试用例。每个测试用例的第一行包含一个整数 n (1 ≤ n ≤ 1000) — 学生人数。
接下来是 n 行。每行包含两个整数 li, ri (1 ≤ li ≤ ri ≤ 5000) - 第二个第 i 个学生来到队列末尾,如果他仍然拿不到茶,则第二个学生离开队列。
保证对于每个 $$i \in [2; n]$$ 条件 li - 1 ≤ li 成立。
所有测试用例的 n 总和不超过 1000。
请注意,在 hacks 中你必须设置 t = 1。
输出
对于每个测试用例打印 n 个整数。当第 i 个学生拿到茶时,其中第 i 个必须等于第二个;如果他没有喝茶就离开,则第 i 个必须等于 0。
示例
输入 #1
2 2 1 3 1 4 3 1 5 1 1 2 3
输出 #1
1 2 1 0 2
注意
该示例包含 2 个测试:
1. 第 1 秒,学生 1 和 2 来到队列,学生 1 拿茶。学生 2 在第二秒喝茶。
2. 在第 1 秒内,学生 1 和学生 2 来到队列,学生 1 拿到茶,学生 2 没有茶就离开。第 2 秒,学生 3 过来拿茶。