問題文
Snuke 将参加 IOI(国际反转奥林匹克)h-1我决定带领其他玩家,以小组长的身份参加。
IOI 垂直 领导者和玩家共同解决大小为 h× 横 w 的反转难题。 具体来说,队长和球员h每个人负责一排,只能按下该排的方块。
好吧,IOI大赛终于明天了,但是Snuke因为有急事要回国了。 幸运的是,Manuke君也在队伍中,所以他决定代替Nuke君参加比赛,但由于他很笨,所以他无法解决反转难题。
因此,Nuke-kun 决定制作一台机器,通过输入反转谜题的初始状态和领导者负责的行号,输出 Nuke-kun 应该按下的方块的列号列表。
然而,反转谜题是给定一块涂成黑白的棋盘,每个人在自己负责的行中选择一个方格,目标是反复反转所选方格以及与该方格相邻的方格的黑白,最后使所有方格都变成白色。
入力
输入是按以下格式从标准输入给出的。
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}
第一行的输入是w,h 分别是板上的列数和行数。r 代表领导者负责的行号。
从第二行开始的输入是 关于1≦i≦a,1≦j≦b_i关于质量(x_i,y_{i,j})表示该方块为黑色,其他方块为白色。 对于
- 1 ≦ w ≦ 60
- 1 ≦ h ≦ 1000000000000000000 (=10^{18})
- 1 ≦ r ≦ h
- 1 ≦ a ≦ 100
- 1 ≦ i ≦ a 反对
- 1 ≦ x_i ≦ h
- 1 ≦ b_i ≦ w
- 1 ≦y_{i,1} < y_{i,2} < ... < y_{i,{bi}} ≦w
- x_i ≠ x_j(i ≠ j)
部分点制約
子任务1(10分):w,h ≦10
子任务2(25分):h ≦10000
子任务3(10分):h ≦1000000
子任务4(25分):a ≦10
子任务5(15分):a ≦50
子任务6(15分):没有额外的限制
出力
输出采用以下格式。
n y_1 y_2 ... y_n
你个白痴 r 线 y_1,y_2,...,y_n 当按下一列中的 n 个方格时,如果玩家按下某种方式并且解决了反转难题,则输出被认为是正确的。
但是, y_1,y_2,...,y_n 应按升序输出。 (15:13)
但是,有一个唯一的输出满足给定输入的条件。
入力例1
3 3 1 3 1 1 2 2 1 1 3 1 3
出力例1
1 2
入力例2
3 3 2 3 1 1 2 2 1 1 3 1 3
出力例2
2 1 3
入力例3
3 3 3 3 1 1 2 2 1 1 3 1 3
出力例3
2 2 3
入力例4
10 10 5 3 3 2 5 7 5 4 1 4 6 9 6 1 10
出力例4
5 2 4 5 6 10