Problem Description

Snuke-kun has been appointed as the leader of a delegation to the IOI (International Olympiad in Inverting), where he will lead $h-1$ contestants.

At the IOI, a reversal puzzle of size $h \times w$ will be solved collaboratively by the leader and the contestants. Specifically, a total of $h$ people, including the leader and contestants, will be responsible for one row each, and they can only press the squares in their row.

The competition is set to start tomorrow, but Snuke-kun has to return to his country urgently. Fortunately, Manuke-kun is also traveling with the team, so he will participate in the competition in Snuke-kun's place. However, Manuke-kun is not very clever and cannot solve the reversal puzzle.

Therefore, Snuke-kun decided to create a machine that, upon inputting the initial state of the reversal puzzle and the row number assigned to the leader, will output a list of column numbers of the squares that Manuke-kun should press.

The reversal puzzle involves a board painted in black and white. Each person is responsible for selecting squares in their row, and upon selection, the color of the selected square and all adjacent squares (connected by edges) will be inverted. The goal is to eventually turn all squares white.

Input Format

The input is given from the standard input in the following format:

$w$ $h$ $r$ $a$ $x_1$ $b_1$ $y_{1,1}$ $y_{1,2}$ ... $y_{1,b1}$ ... ... $x_a$ $b_a$ $y_{a,1}$ $y_{a,2}$ ... $y_{a,b_a}$

The first line of input contains $w$ and $h$, which represent the number of columns and rows of the board, respectively, and $r$, which is the row number assigned to the leader.

The subsequent lines of input indicate that for $1 \leq i \leq a$ and $1 \leq j \leq b_i$, the square $(x_i, y_{i,j})$ is a black square, and all other squares are white.

• $1 \leq w \leq 60$
• $1 \leq h \leq 1000000000000000000$ ($= 10^{18}$)
• $1 \leq r \leq h$
• $1 \leq a \leq 100$
• For $1 \leq i \leq a$:
• $1 \leq x_i \leq h$
• $1 \leq b_i \leq w$
• $1 \leq y_{i,1}$
• $x_i \neq x_j$ ($i \neq j$)

Partial Points Constraints

subtask1 (10 points): $w, h \leq 10$

subtask2 (25 points): $h \leq 10000$

subtask3 (10 points): $h \leq 1000000$

subtask4 (25 points): $a \leq 10$

subtask5 (15 points): $a \leq 50$

subtask6 (15 points): No additional constraints

Output Format

None

Sample Input and Output

Sample Input #1

3 3 1
3
1 1 2
2 1 1
3 1 3

Sample Output #1

1 2

Sample Input #2

3 3 2
3
1 1 2
2 1 1
3 1 3

Sample Output #2

2 1 3

Sample Input #3

3 3 3
3
1 1 2
2 1 1
3 1 3

Sample Output #3

2 2 3

Sample Input #4

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

Sample Output #4

5 2 4 5 6 10

Notes/Hints

Sample Explanation 3

Input Example #4

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

Output Example #4

5 2 4 5 6 10

见题面 Input 部分

见题面 Output 部分