AT_ijpc2015_g.IOI

すぬけ君将作为团长，带领 $h-1$ 名选手参加 IOI（International Olympiad in Inverting）。

在 IOI 中，团长和选手们需要协作解决一个纵向 $h$ 行、横向 $w$ 列的反转谜题。具体来说，团长和选手共 $h$ 人，每人负责一行，只能按下自己负责行的格子。

眼看 IOI 比赛就在明天，すぬけ君却因急事不得不回国。幸运的是，まぬけ君也随队同行，可以代替すぬけ君参加比赛，但由于まぬけ君很“まぬけ”，他不会解反转谜题。

因此，すぬけ君决定制作一台机器，只要输入反转谜题的初始状态和团长负责的行号，就能输出まぬけ君应按下的格子的列号列表。

反转谜题的规则如下：给定一个由黑白两色组成的棋盘，每人可以选择自己负责行的格子，每次按下一个格子时，该格子及其与之边相邻的格子的颜色都会反转。目标是通过若干次操作，使所有格子最终变为白色。

输入通过标准输入给出，格式如下：

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

第一行输入中，$w, h$ 分别表示棋盘的列数和行数，$r$ 表示团长负责的行号。

从第二行开始，棋盘的初始状态以如下方式给出：对于 $1 \leq i \leq a, 1 \leq j \leq b_i$，格子 $(x_i, y_{i,j})$ 为黑色，其余格子为白色。

• $1 \leq w \leq 60$
• $1 \leq h \leq 1000000000000000000\ (=10^{18})$
• $1 \leq r \leq h$
• $1 \leq a \leq 100$
• 对于 $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)$

部分分约束：

• subtask1 (10 分)：$w, h \leq 10$
• subtask2 (25 分)：$h \leq 10000$
• subtask3 (10 分)：$h \leq 1000000$
• subtask4 (25 分)：$a \leq 10$
• subtask5 (15 分)：$a \leq 50$
• subtask6 (15 分)：无额外约束

请输出まぬけ君应按下的格子的列号列表，按升序排列，空格分隔。

样例解释 3

输入例 4

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

输出例 4

2 4 5 6 10

由 ChatGPT 4.1 翻译