说明

2018 年，国际信息学奥林匹克竞赛（IOI）将在日本举办。为了庆祝这一盛事，IOI 组委会计划制作一件“略显奇特设计”的艺术品，并用它来装饰比赛场地。组委会委托 JOI（Just Odd Inventions）有限公司进行设计。JOI 的设计师们提出了以下方案：

• 艺术品将制作在一个 $H \times W$ 的矩形网格板上。我们将用 $N$ 个瓷砖铺满整个网格板。瓷砖之间不能重叠。
• 第 $i$ 个（$1 \leq i \leq N$）瓷砖的尺寸要么是 $1 \times 1$，要么是 $1 \times 2$。瓷砖 $i$ 的颜色为 $C_i$。
• 我们可以旋转 $1 \times 2$ 的瓷砖，将其作为 $2 \times 1$ 的瓷砖使用。

此外，他们还提出了艺术品所用瓷砖的种类。然而，作为设计中最关键的部分，他们并未提出如何在网格板上铺设瓷砖。由于 JOI 提出的设计总是很美观，组委会决定采纳 JOI 关于瓷砖种类的方案。组委会现在需要思考如何在网格板上铺设瓷砖。他们决定以最大化设计的美观度为目标来铺设瓷砖。

设计的美观度计算方式如下：

• 对于网格中每一条被颜色为 $j$ 和颜色为 $k$ 的两个瓷砖共同占据的单元格边，该边的得分为 $A_{j,k}$。
• 设计的美观度即为网格板上所有单元格边的得分总和。

如果两块 $1 \times 2$ 的瓷砖共享了相邻两个单元格的边，这两条边的得分需要分别计算。

你需要计算出一个能使美观度尽可能大的瓷砖铺设方案。

任务

给定网格板的大小、每个瓷砖的尺寸和颜色，以及美观度的计算方式，请确定一个能使美观度尽可能大的瓷砖铺设方案。

输入格式

共有五个子任务。每个子任务对应一个公开的输入数据文件。每个输入数据文件的格式如下。

• 输入的第一行包含四个以空格分隔的整数 $H, W, K, N$。这表示矩形网格板由 $H \times W$ 个单元格组成，瓷砖共有 $K$ 种颜色，设计中将使用 $N$ 块瓷砖。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含两个以空格分隔的整数 $S_i, C_i$。这表示瓷砖 $i$ 的尺寸为 $1 \times S_i$，颜色为 $C_i$。
• 接下来的 $K$ 行中，第 $j$ 行（$1 \leq j \leq K$）包含 $K$ 个以空格分隔的整数 $A_{j,1}, A_{j,2}, \dots, A_{j,K}$。这表示当颜色为 $j$ 和颜色为 $k$ 的两块瓷砖共享一条边时，该边的得分为 $A_{j,k}$。

输出格式

你需要为每个输入数据文件提交一个对应的输出数据文件。输出数据文件应由 $N$ 行组成。第 $i$ 行（$1 \leq i \leq N$）按以下格式描述瓷砖 $i$ 的放置方式。

• 当 $S_i = 1$ 时，第 $i$ 行应包含两个以空格分隔的整数 $A_i, B_i$。这表示瓷砖 $i$ 被放置在从上往下数第 $A_i$ 行、从左往右数第 $B_i$ 列的单元格上。
• 当 $S_i = 2$ 时，第 $i$ 行应包含四个以空格分隔的整数 $A_i, B_i, C_i, D_i$。这表示瓷砖 $i$ 被放置在网格板上，覆盖了从上往下数第 $A_i$ 行、从左往右数第 $B_i$ 列的单元格，以及从上往下数第 $C_i$ 行、从左往右数第 $D_i$ 列的单元格。

3 2 3 4
1 1
2 2
1 3
2 1
2 7 5
7 4 3
5 3 1

2 2
1 1 1 2
3 2
3 1 2 1

提示

样例 1 解释

在此样例输入中，设计用的网格板大小为 $3 \times 2$，共使用 4 块瓷砖。每块瓷砖的颜色和尺寸如下：

因此，有一块颜色为 1 的 $1 \times 1$ 瓷砖，一块颜色为 2 的 $1 \times 2$ 瓷砖，一块颜色为 3 的 $1 \times 1$ 瓷砖，以及一块颜色为 1 的 $1 \times 2$ 瓷砖。

我们按照以下方式铺设瓷砖。图中的数字表示瓷砖的编号。

:::align{center} :::

设计的美观度计算如下，最终美观度为 26。

• 由于颜色为 2 的瓷砖 2 与颜色为 1 的瓷砖 4 共享一条边，得到得分 7。
• 由于颜色为 2 的瓷砖 2 与颜色为 1 的瓷砖 1 共享一条边，得到得分 7。
• 由于颜色为 1 的瓷砖 4 与颜色为 1 的瓷砖 1 共享一条边，得到得分 2。
• 由于颜色为 1 的瓷砖 4 与颜色为 3 的瓷砖 3 共享一条边，得到得分 5。
• 由于颜色为 1 的瓷砖 1 与颜色为 3 的瓷砖 3 共享一条边，得到得分 5。

约束条件

所有输入数据满足以下条件。

• $1 \leq H \leq 100$。
• $1 \leq W \leq 100$。
• $1 \leq K \leq 100$。
• $1 \leq N \leq 10\,000$。
• $1 \leq S_i \leq 2$（$1 \leq i \leq N$）。
• $1 \leq C_i \leq K$（$1 \leq i \leq N$）。
• $H \times W = S_1 + S_2 + \dots + S_N$。
• $0 \leq A_{j,k} \leq 1000$（$1 \leq j \leq K, 1 \leq k \leq K$）。
• $A_{j,k} = A_{k,j}$（$1 \leq j \leq K, 1 \leq k \leq K$）。

子任务

对于每个子任务，$H$、$W$、$K$、$N$ 的值如下表所示。关于 $X$ 和 $Y$ 的具体含义，请参见评分细则。

评分细则

这是一个提交答案任务。共有五个子任务，每个子任务包含一个输入数据文件。你需要为每个子任务提交一个对应的输出数据文件。每个子任务的得分计算方式如下：

• 如果瓷砖的铺设方式不满足输出文件的格式要求，得分为 0。
• 如果瓷砖的铺设方式满足输出文件的格式要求，则根据 $X$ 和 $Y$ 的值按下述方式计算得分。设 $B$ 为该铺设方案的设计美观度。
  • 如果 $B < X$，得分为 0。
  • 如果 $X \leq B < Y$，得分为 $\left\lfloor 1 + 19 \times \left( \frac{B - X}{Y - X} \right)^2 \right\rfloor$。其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。
  • 如果 $Y \leq B$，得分为 20。

翻译由 DeepSeek V3.2 完成