← 返回题目列表

Codeforces · 1571/I

I. 体检

中文机器翻译题面 查看原题

波利卡普计划在当地诊所接受全面体检。有 $$$n$$$ 名医生,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 医生从 $$$L_i$$$ 分钟到 $$$R_i$$$ 分钟接诊病人,因此 Polycarp 可以在此范围内的任何分钟去看他。每位医生只需要一分钟来检查波利卡普的健康状况。

Polycarp 希望在某个分钟到达诊所 $$$x$$$ 并按某种顺序拜访所有 $$$n$$$ 医生,而无需多次等待或拜访任何医生。

更正式地说,他选择一个整数 $$$x$$$ 和一个排列 $$$p_1, p_2, \dots, p_n$$$ (从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 整数序列,使得每个整数只出现一次),然后继续访问:

- 医生 $$$p_1$$$ 在 $$$x$$$ 分钟;
- 医生 $$$p_2$$$ 在 $$$x+1$$$ 分钟;
- ...
- 医生 $$$p_n$$$ 在 $$$x+n-1$$$ 分钟。

第 $$$p_i$$$ 位医生应该能够在 $$$x+i-1$$$ 分钟接诊病人,因此以下内容应该成立:$$$L[p_i] \le x + i - 1 \le R[p_i]$$$。

确定 Polycarp 是否可以选择这样一个分钟 $$$x$$$ 和一个排列 $$$p$$$,使他能够拜访所有 $$$n$$$ 医生,而无需多次等待或拜访任何医生。如果有多个答案,请打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 医生的数量。

测试用例的第二行包含 $$$n$$$ 整数 $$$L_1, L_2, \dots L_n$$$ ($$$1 \le L_i \le 10^9$$$)。

测试用例的第三行包含 $$$n$$$ 整数 $$$R_1, R_2, \dots R_n$$$ ($$$L_i \le R_i \le 10^9$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例打印一个答案。

如果存在这样一个分钟 $$$x$$$ 和排列 $$$p$$$ 使得 Polycarp 能够拜访所有 $$$n$$$ 医生而无需多次等待或拜访任何医生,则在第一行中打印 $$$x$$$ 并在第二行中打印排列 $$$p$$$ 。如果有多个答案,请打印其中任何一个。

否则,在唯一的行中打印$$$-1$$$。

示例

输入 #1

5
3
2 3 1
3 3 2
8
6 6 5 4 9 4 3 6
7 6 10 6 9 6 6 8
2
4 2
4 2
3
2 2 2
3 3 3
1
5
10

输出 #1

1
3 1 2 
3
7 4 6 2 1 8 5 3 
-1
-1
7
1

注意

在第三个测试用例中,不可能拜访所有医生,因为 Polycarp 必须在 $$$2$$$ 分钟拜访医生 $$$2$$$,并在 $$$4$$$ 分钟拜访 $$$1$$$ 医生。然而,这需要他在两次访问之间等待一分钟,这是不允许的。

在第四个测试用例中,所有医生在 $$$2$$$ 分钟内接诊患者。然而,由于他们是三个人,波利卡普无法全部拜访他们。