Under construction

Still being built. Things may change

Pick Your Own Nim

Time limit2sMemory limit512 MB

Summary
Bob picks one heap from each of his boxes so that he wins for every nonempty subset Alice can choose from her heaps, or the task reports that he cannot.
Level

Hard8 of 10

Topics
Bit manipulation, Math, Implementation
Solved
No attempts yet

Statement

Alice and Bob love playing Nim. If the heaps are a1,…,ana_1, \ldots, a_n, the first player wins if and only if a1⊕⋯⊕ana_1 \oplus \cdots \oplus a_n is nonzero. Some online games let players pick their characters before the match, so they made a new version. Each of them has several boxes of heaps. In the first phase, each player picks exactly one heap from each of their boxes. In the second phase, Alice chooses a nonempty subset of the heaps she picked, and regular Nim starts on the chosen heaps with Bob to move first. Bob already knows which heaps Alice picked. Help him choose his heaps so that he wins no matter which subset Alice chooses.

Input

The first line contains the number of heaps nn picked by Alice (0≤n≤600 \le n \le 60). If n>0n > 0, the next line contains the nn heap sizes. If n=0n = 0, that line is omitted. The next line contains the number of Bob's boxes mm (1≤m≤601 \le m \le 60). Each of the next mm lines describes one box. It starts with kik_i (1≤ki≤50001 \le k_i \le 5000), the number of heaps in the box, followed by the kik_i heap sizes. Each heap size is between 11 and 260−12^{60}-1, inclusive. The total number of heaps in Bob's boxes is at most 5000.

Output

If Bob cannot win, meaning that no matter which heaps he picks, Alice can choose a subset that leaves the resulting Nim position losing, print −1-1. Otherwise, print mm integers: the sizes of the heaps Bob should pick from his boxes, in the same order as the boxes are given in the input.

Hint

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

Examples2

  1. Example 1

    Input
    2
    1 2
    2
    2 1 2
    3 1 2 3
    
    Expected output
    -1
    
  2. Example 2

    Input
    1
    5
    2
    3 1 2 3
    4 4 5 6 7
    
    Expected output
    1
    6