你的老板让你为他的会议安排一个有效的日程。他有 $n$ 场会议，其中第 $i$ 场会议必须在时间区间 $[l_i, r_i]$ 内开始并结束，时间以小时为单位。每场会议恰好持续一小时，显然你的老板不能同时参加两场会议。

作为一名竞赛程序员，你已经无数次解决过这种经典的调度问题，而这一次，你终于意识到它是完全不切实际的。一个人怎么可能在没有时间往返于不同地点、也没有任何休息的情况下参加超过十万场会议呢？每场会议都恰好持续一小时是不可能的——根据经验——而且肯定会有会议因为有人迟到而推迟开始。

这些根深蒂固的哲学问题可能是人类面临的大问题，但既然你不必亲自参加这些会议，你根本不在乎解决所有这些问题。然而，给你的老板留下深刻印象对你来说肯定是有价值的，所以你尝试至少稍微改进一下这个日程。

请找到任意一个满足每两场会议之间至少间隔一小时的日程安排，或者报告不存在这样的安排。这肯定只是对经典问题的一个微不足道的改动，对吧？

输入格式

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$ ($1 \le t \le 10^5$) —— 测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$) —— 会议的数量。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i < r_i \le 10^6$) —— 第 $i$ 场会议必须开始和结束的时间区间。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

如果不存在有效的日程安排，则输出 $-1$。否则，输出 $n$ 个整数 $a_i$，表示第 $i$ 场会议的开始时间。

样例

输入 1

4
3
1 3
1 7
2 4
2
1 2
2 3
4
1 5
2 6
3 4
4 7
2
1 5
2 3

输出 1

1 5 3
-1
-1
4 2

说明

在第一个测试用例中，第一场会议在第 1 小时开始，持续一小时，直到第 2 小时开始。之后，你的老板休息一小时，直到第 3 小时开始参加第三场会议，持续到第 4 小时。然后，他再休息一小时，直到第 5 小时开始参加第二场会议，持续到第 6 小时。

注意，第三场会议不可能在第 4 小时开始，因为这样该会议会在第 5 小时结束。