問題文

すぬけ君はIOI(International Olympiad in Inverting)に$h-1$人の選手を引率して団長として参加することになった。

IOIでは縦 $h×$ 横 $w$ の大きさの反転パズルを団長と選手が協力して解く。 具体的には団長と選手合わせて$h$人がそれぞれ1行ずつ担当し、その行のマス目だけ押すことができる。

さて、IOIのコンテストはいよいよ明日になったがすぬけ君は急用で帰国しなければならなくなった。 幸いまぬけ君もチームに同行していたのですぬけ君の代わりにコンテストに参加してくれることになったが、まぬけ君はまぬけなので反転パズルを解くことができない。

そこですぬけ君は反転パズルの初期状態と団長の担当する行番号を入力するとまぬけ君の押すべきマス目の列番号の一覧を出力してくれる機械を作ることにした。

ただし、反転パズルとは白黒に塗られた盤面が与えられ、各人が担当する行のマスを選び、選ばれたマス及びそのマスに辺で隣接するマスの白黒を反転することを繰り返し、最終的にすべてのマスを白にすることを目的とするパズルである。

---

入力

入力は以下の形式で標準入力から与えられる。

$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)$

部分点制約

subtask1(10点):$w,h ≦10$

subtask2(25点):$h ≦10000$

subtask3(10点):$h ≦1000000$

subtask4(25点):$a ≦10$

subtask5(15点):$a ≦50$

subtask6(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

---