← 返回题目列表

Codeforces · 1783/E

E. 年度最佳游戏

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

Monocarp 和 Polycarp 正在玩电脑游戏。该游戏有 $$$n$$$ 头目可供玩家杀戮,编号从 $$$1$$$ 到 $$$n$$$。

他们将通过以下方式与每个老板战斗:

- Monocarp 尝试杀死 Boss $$$k$$$;
- 波利卡普 $$$k$$$ 尝试杀死 Boss;
- Monocarp 尝试杀死 Boss $$$k$$$;
- 波利卡普 $$$k$$$ 尝试杀死 Boss;
- ...

Monocarp 在第 $$$a_i$$$ 次尝试中杀死了第 $$$i$$$ 次首领。波利卡普在第 $$$b_i$$$ 次尝试中杀死了第 $$$i$$$ 次首领。其中一人杀死第 $$$i$$$ 个首领后,他们会继续攻击第 $$$(i+1)$$$ 个首领。他们两人的尝试计数器都会重置。一旦他们中的一个杀死了第 $$$n$$$ 个头目,游戏就结束了。

找到 $$$k$$$ 从 $$$1$$$ 到 $$$n$$$ 的所有值,这样 Monocarp 就能杀死所有 Boss。

输入

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

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

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) - Monocarp 杀死每个 boss 的尝试索引。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$) - 波利卡普杀死每个 Boss 的尝试索引。

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

输出

对于每个测试用例,打印两行。第一行应包含一个整数 $$$\mathit{cnt}$$$ — 从 $$$1$$$ 到 $$$n$$$ 的 $$$k$$$ 值的数量,这样 Monocarp 就能杀死所有 Boss。第二行应包含 $$$\mathit{cnt}$$$ 不同的整数 - $$$k$$$ 本身的值。

示例

输入 #1

3
3
1 1 1
2 3 1
1
1
1
4
1 4 3 2
3 3 4 1

输出 #1

3
1 2 3 
1
1 
2
2 4

注意

考虑示例的最后一个测试用例。

让 $$$k = 1$$$。首先,Monocarp 尝试杀死第一个 Boss。它成功了,因为 $$$a_1 = 1$$$。然后,Monocarp 尝试杀死第二个 Boss。它不成功,因为 $$$a_2 > 1$$$。于是,坡旅甲做出了尝试。它也不成功,因为 $$$b_2 > 1$$$。然后,Monocarp 再次尝试。它仍然不成功,因为 $$$a_2 > 2$$$。这种情况一直持续到波利卡普最终在第三次尝试中杀死了 Boss。 Monocarp 没有杀死这个 Boss,因此 $$$k = 1$$$ 不是答案。

让 $$$k = 2$$$。 Monocarp 仍然在第一次尝试时杀死了第一个 Boss。然后,他对第二个boss进行了两次尝试,但均未成功。然后,波利卡普进行了两次失败的尝试。然后,Monocarp 又进行了两次尝试,并在第四次尝试中杀死了 Boss。第三个boss也类似。首先,Monocarp 的两次尝试均未成功。然后,坡旅甲两次尝试均未成功。然后,Monocarp 又进行了两次尝试,但即使他的第一次也成功了,因为 $$$a_3 = 3$$$。第四个boss也被Monocarp杀死。因此,$$$k = 2$$$ 就是答案。