Duty Free Shop

Interview

Time limit1sMemory limit128 MB

Summary

Assign each box entirely to one of two brands so both totals stay within limits, printing the greedy canonical assignment or Impossible to distribute.

Level: Medium6 of 10
Topics: Greedy, Dynamic programming, Sorting, Implementation
Solved: No attempts yet

Problem

Pedro travelled to Europe to take part in the International Olympiad in Informatics and is now coming back home. Since all of his friends asked him to bring a gift, he bought two big bags of chocolates: one of brand Mindt and one of brand Lilka. Each bag contains a certain number of small chocolates, and buying the two big bags was much cheaper than buying smaller, individual boxes.

At home Pedro has some empty chocolate boxes that he kept from earlier trips. He wants to repack the chocolates he just bought into these smaller boxes so he can give them to his friends.

As soon as he starts filling the boxes he realises there is a problem: he has two different brands, and if he mixes chocolates of different brands in one box, the friend who receives that box will notice his money-saving trick and be displeased.

Help Pedro distribute the chocolates so that every box is completely full and contains chocolates of only one brand. Some chocolates may be left over (Pedro keeps those for himself).

Input

The input contains several test cases. Each test case consists of three lines.

The first line contains two integers $M$ and $L$ ( $0 \le M, L \le 1000$ ): the number of Mindt and Lilka chocolates Pedro bought, respectively.
The second line contains one integer $N$ ( $N \le M+L$ ): the number of empty boxes.
The third line contains $N$ integers; the $i$ -th of them is the capacity $C_i > 0$ of box $i$ (the number of chocolates needed to fill it completely).

The input ends with a line containing $M = L = 0$ , which must not be processed.

Output

Every box must be completely full and hold a single brand, so each box is assigned either to Mindt or to Lilka. A distribution is valid when the total capacity of the Mindt boxes is at most $M$ and the total capacity of the Lilka boxes is at most $L$ .

For each test case print one line.

If no valid distribution exists, print Impossible to distribute.

Otherwise several valid distributions may exist, so to make the answer unique print the canonical distribution defined as follows. Consider the boxes one by one from box $1$ to box $N$ ; assign the current box to Mindt if, after doing so, the remaining boxes can still be assigned to make the whole distribution valid, and assign it to Lilka otherwise. Then print the number of boxes assigned to Mindt, followed by their box numbers in ascending order, all separated by single spaces. (If no box is assigned to Mindt, print just 0.)

Examples3

Example 1

Input

12 9
4
5 2 8 5
100 120
5
21 32 110 54 3
0 0

Expected output

3 1 2 4
Impossible to distribute

Example 2
Input
```
10 0
2
4 6
0 0
```
Expected output
```
2 1 2
```
Example 3
Input
```
0 10
2
4 6
0 0
```
Expected output
```
0
```