← 返回题目列表

AtCoder · code_thanks_festival_14_quala_e

E. 仪式

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

問題文

在某个神社,每年都会举行跨年仪式。

仪式上使用 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