Magic Polynomial Partition

You are given an even number n of distinct integers representing scores of WA (Wrong Answer) submissions, and an integer d. Consider a polynomial function defined as:

$$f(x)=a_1x^0+a_2x^1+\cdots+a_d x^{d-1},$$

where the coefficients a_i can be any real numbers. Two groups of scores are considered magically equivalent if for any choice of coefficients, the sums of f(x) over the scores in each group are equal. Because the coefficients are arbitrary, this condition is equivalent to requiring that for every exponent k from 0 to d-1 the following holds:

$$\sum_{x\in A}x^k = \sum_{x\in B}x^k.$$

Your task is to partition the given set of n scores into two groups of equal size such that the power sums (for exponents 0 through d-1) of the two groups are equal.

If such a partition exists, output the two groups (each group sorted in ascending order) on two separate lines. If more than one valid partition exists, output any one of them. If no valid partition exists, output -1.

Example:

For n = 8 and d = 3, consider the scores: {1, 2, 3, 4, 5, 6, 7, 8}. A valid partition is:

• A = {1, 4, 6, 7}
• B = {2, 3, 5, 8}

Verification for the polynomial f(x)=x^0+x^1+x^2 (i.e. with all coefficients 1):

• For A: 1^0+4^0+6^0+7^0 = 4, 1+4+6+7 = 18, 1+16+36+49 = 102
• For B: 1+1+1+1 = 4, 2+3+5+8 = 18, 4+9+25+64 = 102

Since the corresponding power sums are equal, the partition is valid.

inputFormat

The first line contains two integers n (an even number, 2 ≤ n ≤ 16) and d (1 ≤ d ≤ n), separated by a space.

The second line contains n distinct integers representing the scores.

outputFormat

If a valid partition exists, output two lines:

• The first line contains the scores in group A in ascending order, separated by spaces.
• The second line contains the scores in group B in ascending order, separated by spaces.

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

sample

8 3
1 2 3 4 5 6 7 8

1 4 6 7
2 3 5 8

</p>