A10241 | Double Knapsack

You are given two multisets $A$ and $B$ . Each multiset has exactly $n$ integers each between $1$ and $n$ inclusive. Multisets may contain multiple copies of the same number.

You would like to find a nonempty subset of $A$ and a nonempty subset of $B$ such that the sum of elements in these subsets are equal. Subsets are also multisets, i.e. they can contain elements with equal values.

If no solution exists, print $-1$ . Otherwise, print the indices of elements in any such subsets of $A$ and $B$ that have the same sum.

The first line of the input contains a single integer $n$ ( $1<=n<=1000000$ ) — the size of both multisets.

The second line contains $n$ integers, denoting the elements of $A$ . Each element will be between $1$ and $n$ inclusive.

The third line contains $n$ integers, denoting the elements of $B$ . Each element will be between $1$ and $n$ inclusive.

If there is no solution, print a single integer $-1$ . Otherwise, your solution should be printed on four lines.

The first line should contain a single integer $k_{a}$ , the size of the corresponding subset of $A$ . The second line should contain $k_{a}$ distinct integers, the indices of the subset of $A$ .

The third line should contain a single integer $k_{b}$ , the size of the corresponding subset of $B$ . The fourth line should contain $k_{b}$ distinct integers, the indices of the subset of $B$ .

Elements in both sets are numbered from $1$ to $n$ . If there are multiple possible solutions, print any of them.