D. Pick Your Own Nim
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Alice and Bob love playing the Nim game (if you do not remember the rules, please refer to the Notes section). They played it so many times that they learned how to determine the winner at a first glance: if there are $$$a_1$$$, ..., $$$a_n$$$ stones in the heaps, the first player wins if and only if the bitwise xor $$$a_1 \oplus \ldots \oplus a_n$$$ is nonzero.

They heard that in some online games players pick their characters before the game, adding a strategic layer. Why not do it with Nim?

They came up with the following version. Alice and Bob each have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

Input

On the first line, there is a single integer $$$n$$$ ($$$0 \leq n \leq 60$$$), the number of heaps picked by Alice.

If $$$n > 0$$$, on the next line there are $$$n$$$ integers: the sizes of those heaps. Otherwise, this line is omitted.

On the next line there is a single number $$$m$$$ ($$$1 \leq m \leq 60$$$), the number of Bob's boxes.

Each of the next $$$m$$$ lines contains the description of a box. Each description starts with a number $$$k_i$$$ ($$$1 \leq k_i \leq 5000$$$), the number of heaps in the box. Then $$$k_i$$$ numbers follow, denoting the sizes of those heaps.

The size of each heap is between $$$1$$$ and $$$2^{60} - 1$$$, inclusive. The total number of heaps in Bob's boxes does not exceed $$$5000$$$.

Output

If Bob cannot win (that is, no matter what he picks, Alice can make such a choice that the resulting Nim position is losing), print "-1" (without quotes). Otherwise, print $$$m$$$ integers: the sizes of the heaps Bob should pick from his boxes in the same order in which the boxes are given in the input.

Examples
Input
2
1 2
2
2 1 2
3 1 2 3
Output
-1
Input
1
5
2
3 1 2 3
4 4 5 6 7
Output
1
6
Note

In the game of Nim, there are several heaps of stones. On each turn, the player selects any heap and takes some positive number of stones from it. The player who takes the last stone wins the game.