给定两个多重集 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