Equal Tastiness Partition

This problem is an interactive I/O problem where you must first place orders for cookies and then assign some of the delivered cookies to two sisters. Each cookie has a distinct integer tastiness value between \(1\) and \(10^{16}\). Although the ordering phase is interactive, in this version you are given the final set of delivered cookies.

Specifically, you are given two integers \(n\) and \(m\) on the first line. Here, \(n\) is the fixed number of cookies in each order (which does not affect the partition process) and \(m\) is the number of orders placed (i.e. the number of delivered cookies). The second line contains \(m\) distinct integers representing the tastiness values of the delivered cookies.

Your task is to select a subset of these cookies and partition it into two non-empty groups such that the sum of tastiness values of each group is equal. You are allowed to leave some cookies unassigned. If a valid partition exists, output the 1-indexed positions of the cookies assigned to the first sister (in one line) and the positions assigned to the second sister (in the next line). If there are multiple valid answers, you may output any one of them. If no such partition exists, output -1.

Note: In the original interactive problem you would decide on the orders interactively. Here, the ordering phase is already done and you only have to perform the partitioning.

inputFormat

The first line contains two integers \(n\) and \(m\):

• \(n\): the number of cookies in each order (unused in the partition logic).
• \(m\): the number of delivered cookies (i.e. orders placed).

The second line contains \(m\) distinct space-separated integers \(a_1, a_2, \dots, a_m\), where each \(a_i\) represents the tastiness of the \(i\)-th delivered cookie.

outputFormat

If a valid partition exists, output two lines:

• The first line contains the 1-indexed positions of the cookies assigned to the first sister, separated by spaces.
• The second line contains the 1-indexed positions of the cookies assigned to the second sister, separated by spaces.

If no valid partition exists, output a single line with -1.

sample

3 4
10 4 6 8

1
2 3