Problem J
Treasure Trouble

When Theta was younger, one of her favorite games was “Treasure Trouble,” a boardgame for children 5 and up, which is made by Noris-Spiele. In this game, players are pirates whose goal it is to collect treasures. At the beginning of each round, an hourglass is turned over and the youngest player shouts: “For the Cap’n,” after which the players start filling their treasure chests with loot of various shapes, colors, and sizes before the hourglass runs out. After the time has run out, each chest is carefully checked to make sure its lid lies flush on top — any items too large to fit must be removed. Each player receives $1$ point for each item they were able to place into their chest.

There is a twist, however: before the points are counted, a card (chosen from a deck of cards) is flipped over. This card shows treasures of various shapes, colors, and sizes. All treasures that are listed on the card must be given to Jewel Jack (and thus do not count for the player who put them in their chest!)

Given a set of cards, find the optimal strategy for one player to fill their chest such that the expected number of points is maximized!

Input

The input consists of a single test case. The first line of this test case contains three integers $S$ ($1 \le S \le 1000$), $T$ ($1 \le T \le 40$), and $C$ ($0 \le C \le 25$). $S$ is the size of the treasure chest, $T$ is the number of available treasures, and $C$ is the number of cards that may be drawn. Treasures are numbered from $1 \ldots T$. The next line contains $T$ integers denoting the sizes of the available treasures $s_ i$ ($0 < s_ i \le 1000$).

This is followed by $C$ lines, one for each card. Each line starts with an integer $k$ that denotes the number of integers to follow. Each integer specifies the number of a treasure that is displayed on that card (and which does not count for the player if this card is drawn).

Output

Output a selection of treasures such that the expected number of points is maximized. Refer to each treasure using its number ($1 \ldots T$). You may output the treasures in any order. If there is more than one selection of treasures that maximizes the expected gain, you may output any of them.

Sample Input 1 Explanation

In Sample Input 1, there are $4$ items from which to choose to place into a chest of size $50$. Treasure #1 (of size 10) is listed on cards 2 and 3, treasure #2 (of size 20) is listed on cards 1, 2, and 4, treasure #3 (of size 30) is listed on card 1, and treasure #4 (of size 40) is listed on cards 3 and 4. Based on their sizes, we can place treasures $1$, $2$, $3$, $4$, $1 + 2$, $1 + 3$, $1 + 4$, or $2 + 3$ in the chest (where $+$ denotes ‘and’). The table below shows how many points we can expect for each choice.

We choose                    | 1 | 2 | 3 | 4 | 1+2 | 1+3 | 1+4 | 2+3 |
-----------------------------+---+---+---+---+-----+-----+-----+-----+-------
If card #1 is drawn, we get  | 1 | 0 | 0 | 1 |  1  |  1  |  2  |  0  | points
If card #2 is drawn, we get  | 0 | 0 | 1 | 1 |  0  |  1  |  1  |  1  | points
If card #3 is drawn, we get  | 0 | 1 | 1 | 0 |  1  |  1  |  0  |  2  | points
If card #4 is drawn, we get  | 1 | 0 | 1 | 0 |  1  |  2  |  1  |  1  | points
-----------------------------+---+---+---+---+-----+-----+-----+-----+-------
Expected number of points     .5  .25 .75  .5  .75   1.25   1     1

50 4 4
10 20 30 40
2 2 3
2 1 2
2 1 4
2 2 4

1 3

10 10 4
1 1 1 1 2 2 3 3 4 4
6 1 2 3 4 5 6
4 10 1 2 6
4 9 1 2 7
4 3 4 6 8

3 4 5 7 8