← 返回题目列表

AtCoder · ijpc2015_g

D. 国际信息学奥林匹克

中文机器翻译题面 查看原题

問題文

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