← 返回题目列表

Codeforces · 618/F

F. 双背包

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

给定两个多重集 A 和 B。每个多重集正好有 n 个整数,每个整数在 1 到 n 之间(含)。多重集可能包含同一数字的多个副本。

您希望找到 A 的非空子集和 B 的非空子集,使得这些子集中的元素之和相等。子集也是多重集,即它们可以包含具有相等值的元素。

如果不存在解,则打印 - 1。否则,打印 A 和 B 的任何此类子集中具有相同总和的元素的索引。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 1 000 000) — 两个多重集的大小。

第二行包含n个整数,表示A的元素。每个元素都在1和n之间(包括1和n)。

第三行包含n个整数,表示B的元素。每个元素都在1和n之间(包括1和n)。

输出

如果没有解决方案,则打印单个整数 - 1。否则,您的解决方案应打印为四行。

第一行应包含单个整数 ka,即 A 的相应子集的大小。第二行应包含 ka 不同的整数,即 A 的子集的索引。

第三行应包含单个整数 kb,即 B 的相应子集的大小。第四行应包含 kb 个不同的整数,即 B 子集的索引。

两个集合中的元素均从 1 到 n 进行编号。如果有多种可能的解决方案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

1
2
3
5 8 10

输入 #2

5
4 4 3 3 3
2 2 2 2 5

输出 #2

2
2 3
2
3 5