波利卡普计划在当地诊所接受全面体检。有 $$$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$$$ 分钟内接诊患者。然而,由于他们是三个人,波利卡普无法全部拜访他们。