CF618F 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

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.