/ 
実行時間制限: 5 sec / メモリ制限: 256 MB
問題文
ある神殿では毎年、年越しの儀式が行われます。
儀式には R × C 個の石像を用います。石像は縦 (南北方向) に R 行、横 (東西方向) に C 列並んでおり、北西端にある石像を起点として、南に i-1 (1 ≦ i ≦ R) 個、東に j-1 (1 ≦ j ≦ C) 個だけ進んだ場所にある石像を石像 (i,j) と呼ぶことにします。最初、どの石像も南を向いています。
儀式は N 回の手順からなり、それらのうち s (1 ≦ s ≦ N) 回目の手順は以下のようになります。
- 手順 s : r_{a,s} ≦ u ≦ r_{b,s} および c_{a,s} ≦ v ≦ c_{b,s} を満たすすべての整数組 (u,v) について、石像 (u,v) を左に 90 度回転させる。
例年はこの手順を N 回行いますが、今年はある 1 つの手順を忘れてしまっていて、最終結果がいつもと異なるものになってしまいました。
それぞれの手順は重要な意味を持っているのでこのままでは大変なことになってしまいます。
さらに困ったことに、N - 1 回の終了時のそれぞれの石像の向きは記録していませんでした。ただ、幸いなことに終了時に南を向いていた石像の個数が M 個であることがわかりました。
神殿内の会議で、忘れてしまった手順を列挙するプログラムを作成することにしましたが、この神殿にはプログラマーはいませんでした。あなたの課題は、儀式で忘れてしまった手順を列挙するプログラムを作成することです。
入力
入力は以下の形式で標準入力から与えられる。
R C M
N
r_{a,1} r_{b,1} c_{a,1} c_{b,1}
r_{a,2} r_{b,2} c_{a,2} c_{b,2}
:
r_{a,N} r_{b,N} c_{a,N} c_{b,N}
- 1 行目には、石像群の行数 R (1 ≦ R ≦ 50)、列数 C (1 ≦ C ≦ 50) および終了時点で南を向いていた石像の個数 M (0 ≦ M ≦ R × C) が空白区切りで与えられる。
- 2 行目には、手順の個数 N (1 ≦ N ≦ 5,000) が与えられる。
- 3 行目から N 行には、各手順に関する情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には 4 つの整数 r_{a,i}, r_{b,i} (1 ≦ r_{a,i} ≦ r_{b,i} ≦ R), c_{a,i}, c_{b,i} (1 ≦ c_{a,i} ≦ c_{b,i} ≦ C) が空白区切りで与えられる。これは、手順 i が r_{a,i} ≦ u ≦ r_{b,i} および c_{a,i} ≦ v ≦ c_{b,i} を満たすすべての整数組 (u,v) について、石像 (u,v) を左に 90 度回転させる手順であることを表す。
- どの入力についても、少なくとも 1 つの手順は忘れた可能性がある (すなわち、解が少なくとも 1 つは存在する)。
出力
儀式で忘れてしまった手順が昇順に 手順 f_1、手順 f_2、 ... 、手順 f_m であるとしたとき、m 行にわたって出力せよ。m 行のうち l (1 ≦ l ≦ m) 行目には、整数 f_l を出力せよ。出力の末尾にも改行を入れること。
入力例1
3 5 3 6 1 3 2 5 2 2 1 2 1 3 1 4 2 3 2 5 1 2 3 5 1 2 4 5
出力例1
2 6
初期状態では、すべての像の向きは下表のようになっています。
| 南 | 南 | 南 | 南 | 南 |
| 南 | 南 | 南 | 南 | 南 |
| 南 | 南 | 南 | 南 | 南 |
例えば、手順 2 を忘れた場合の挙動は以下のようになります。
手順 1 の後、それぞれの像は
| 南 | 東 | 東 | 東 | 東 |
| 南 | 東 | 東 | 東 | 東 |
| 南 | 東 | 東 | 東 | 東 |
となります。
手順 3 の後、それぞれの像は
| 東 | 北 | 北 | 北 | 東 |
| 東 | 北 | 北 | 北 | 東 |
| 東 | 北 | 北 | 北 | 東 |
となります。
手順 4 の後、それぞれの像は
| 東 | 北 | 北 | 北 | 東 |
| 東 | 西 | 西 | 西 | 北 |
| 東 | 西 | 西 | 西 | 北 |
となります。
手順 5 の後、それぞれの像は
| 東 | 北 | 西 | 西 | 北 |
| 東 | 西 | 南 | 南 | 西 |
| 東 | 西 | 西 | 西 | 北 |
となります。
手順 6 の後、それぞれの像は
| 東 | 北 | 西 | 南 | 西 |
| 東 | 西 | 南 | 東 | 南 |
| 東 | 西 | 西 | 西 | 北 |
となります。
結果として南向きの石像が 3 個となるので、手順 2 は忘れた可能性があります。
この例の場合、他にも手順 6 を忘れた可能性があり、他の場合は個数が矛盾するので、1 行目に 2 を、2 行目に 6 を出力します。
入力例2
4 4 8 9 1 4 1 4 1 4 1 4 1 4 1 1 1 4 3 3 1 2 1 2 1 2 3 4 3 4 1 2 3 4 3 4 1 4 1 4
出力例2
1 2 5 6 7 8 9