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

• 艺术品将制作在一个 $H \times W$ 的矩形板上。我们将用 $N$ 块瓷砖铺满这块板。瓷砖之间不能重叠。
• 第 $i$ 块瓷砖（$1 \le i \le 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 \le i \le N$）包含两个空格分隔的整数 $S_i, C_i$。这意味着第 $i$ 块瓷砖的大小为 $1 \times S_i$，颜色为 $C_i$。
• 接下来的 $K$ 行中，第 $j$ 行（$1 \le j \le K$）包含 $K$ 个空格分隔的整数 $A_{j,1}, A_{j,2}, \dots, A_{j,K}$。这意味着当颜色为 $j$ 和颜色为 $k$ 的两块瓷砖共享一条边时，得分为 $A_{j,k}$。

输出格式

为每个输入数据文件提交一个输出文件。输出文件包含 $N$ 行。第 $i$ 行（$1 \le i \le 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$ 列的单元格。

数据范围

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

• $1 \le H \le 100$
• $1 \le W \le 100$
• $1 \le K \le 100$
• $1 \le N \le 10\,000$
• $1 \le S_i \le 2$ ($1 \le i \le N$)
• $1 \le C_i \le K$ ($1 \le i \le N$)
• $H \times W = S_1 + S_2 + \dots + S_N$
• $0 \le A_{j,k} \le 1\,000$ ($1 \le j \le K, 1 \le k \le K$)
• $A_{j,k} = A_{k,j}$ ($1 \le j \le K, 1 \le k \le K$)

子任务

对于每个子任务，$H, W, K, N$ 的值如下表所示。关于 $X, Y$ 的值，请参阅评分部分。

评分

这是一个仅输出答案的任务。共有五个子任务，每个子任务包含一个输入数据文件。请为每个子任务提交一个输出文件。每个子任务的得分计算如下：

• 如果放置瓷砖的方式不满足输出文件的条件，得分为 0。
• 如果放置瓷砖的方式满足输出文件的条件，得分将根据 $X$ 和 $Y$ 的值计算。设 $B$ 为该铺设方式的设计美感。
  • 如果 $B < X$，得分为 0。
  • 如果 $X \le B < Y$，得分为 $\lfloor 1 + 19 \times (\frac{B - X}{Y - X})^2 \rfloor$。其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。
  • 如果 $Y \le B$，得分为 20。

样例

输入格式 1

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

输出格式 1

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

说明

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

• 编号 1：颜色 1，大小 $1 \times 1$
• 编号 2：颜色 2，大小 $1 \times 2$
• 编号 3：颜色 3，大小 $1 \times 1$
• 编号 4：颜色 1，大小 $1 \times 2$

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

我们按如下方式放置瓷砖。图中的数字表示瓷砖的编号。

设计的美感计算如下。设计的美感为 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。