AT1119 仪式

题目描述

一个神殿每年除夕举行仪式。

仪式上会用 $R\times C$ 个石像。石像是纵向(南北方向) $R$ 行，横向(东西方向) $C$ 列并排的，因此西北端的石像作为起点，向南 $i-1(1\le i\le R)$ 个，向东第 $j-1(1\le j\le C)$ 个石像记为石像 $(i,j)$ 。最初，任何石像都朝南。

• 满足顺序 $s:r_{a,s}\le u\le r_{b,s}$ 及 $c_{a,s}\le v\le c_{b,s}$ 的所有关于石像 $(u,v)$ 的整数组 $(u,v)$ 左转90度。

往年这个顺序进行 $N$ 次，今年的一个顺序忘记了，最终的结果总是不同的。

由于每个顺序都有重要意义，因此这将是一件严肃的事情。

更糟糕的是，第 $N$ 次的结束时的各自的石像的方向是没有记录的。然而，幸运的是结束时发现朝南的石像的个数有 $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\le R\le 50)$ ，列数 $C(1\le C\le 50)$ 及向南的石像个数 $M(0\le M\le R\times C)$ ，用空格分隔。
• 第 $2$ 行包含了顺序的个数 $N(1\le N\le 5,000)$ 。
• 从第 $3$ 行至第 $N+2$ 行包含了各顺序的相关信息。其中第 $i+2(1\le i\le N)$ 行是 $4$ 个整数 $r_{a,i},r_{b,i}(1\le r_{a,i}\le r_{b,i}\le R),c_{a,i},c_{b,i}(1\le c_{a,i}\le c_{b,i}\le C)$ ，用空格分隔。所有整数组 $(u,v)$ 都满足石像 $(u(r_{a,i}\le u\le r_{b,i}),v(c_{a,i}\le v\le c_{b,i}))$ 左旋转90度顺序的步骤。
• 对于任何输入，至少可能有一个输入的顺序是忘记了的(也就是说，至少有一个解是存在的)。

输出格式：

按升序输出仪式中忘记的顺序 $f_1$ 、顺序 $f_2$ 、……、顺序 $f_m$，在 $m$ 行中的第 $l(1\le l \le m)$行输出整数 $f_l$ 。末尾要加换行符。

说明

样例解释 $1$

在初始状态下，所有石像的方向如下表所示。南 南 南 南 南 南 南 南 南 南 南 南 南 南 南。忘记顺序 $2$ 时的行为如下。顺序 $1$ 后，分别向 东 南 东 东 东 东 东 东 东 东 东 东；顺序 $3$ 后，分别向 东 北 北 东 北 东 北 北 东 北 东 北 北 东；顺序 $4$ 后，分别向 东 北 东 北 东 西 西 西 北 西 北 西 西；顺序 $5$后，分别向 东 西 北 西 西 北 西 西 南 西 南 西 西；顺序 $6$ 后，分别向 东 北 西 西 西 西 东 东 东 西 西 西 西 北。结果朝南的石像有 $3$ 个,所以顺序 $2$ 有可能忘记了。在此示例中，还有其它顺序有可能会忘记 $6$ ，而在其他情况下数字相矛盾，所以在第 $1$ 行输出 $2$，第 $2$ 行输出 $6$ 。