Weight Overflow

Time limit1sMemory limit512 MB

Summary

Given n weights and a modulus m, find two disjoint nonempty subsets whose sums are equal modulo m, or report that none exists.

Level: Medium7 of 10
Topics: Brute force, Hash map, Number theory
Solved: No attempts yet

Problem

John recently bought an electronic balance scale from a well-known website. The scale has two plates where you can put items. After you put some items on the scale, it shows which plate is heavier than the other, or that the weights on the two plates are equal and the scale is balanced.

John started experimenting with the scale and found that the results are sometimes strange. The scale adds up the weight of the items on each plate in grams and then compares the two totals. However, the software was written by former sport programmers, so the scale calculates the weight on each plate modulo an integer $m$ .

John has $n$ special weights. The $i$ -th weight has a mass of $a_i$ grams. He wants the scale to balance by putting some of these weights on the plates. He must put at least one weight on the scale.

Input

The first line contains two integers $n$ and $m$ , the number of weights John has and the modulo used for weight calculation ( $1 \le n \le 25$ ; $1 \le m < 4 \cdot 10^7$ ).

The second line contains $n$ integers $a_1, \ldots, a_n$ , the masses of the weights ( $1 \le a_i \le 10^9$ ).

Output

If an answer exists, print $k$ , the number of weights to put on the first plate, on the first line. The second line must contain the numbers of these weights.

Then print $l$ , the number of weights to put on the second plate, on the next line. Print the numbers of these weights on the following line.

Weights are numbered from 1 to $n$ in the order they appear in the input.

If there is no answer, print a single number "-1".

Examples2

Example 1
Input
```
4 14
1 3 7 10
```
Expected output
```
1
4
2
2 3
```
Example 2
Input
```
3 7
1 2 4
```
Expected output
```
3
1 2 3
0
```