说明

这是一个提交答案题。

JOI 王国即将举行全国选举。JOI 王国由 $N$ 个省份组成。

JOI 王国的地图是一个大小为 $H \times W$ 的矩形网格。竖直方向有 $H$ 个格子，水平方向有 $W$ 个格子。一个格子通过其上、下、左、右四条边中的一条与另一个格子相连。这 $H \times W$ 个格子被划分为 $N$ 个省份。每个省份都是由格子组成的连通区域。第 $i$ 个省份（$1 \le i \le N$）总共有 $P_i$ 名选民。

你是 JOI 全国选举委员会的主席。你的任务是将这 $N$ 个省份划分为 $K$ 个选区（$1 \le K \le N$），以便选出 $K$ 名代表。每个选区必须至少包含一个省份，并且属于同一个选区的所有格子需要构成一个连通区域。注意，格子只能通过共享一条边（上、下、左、右）来连通，仅共享一个顶点（对角相邻）的格子不算连通。

对于每个选区，比值 $1 /$（该选区的选民总数）被称为该选区的单票权重。选票价值差异定义为所有选区的最大单票权重除以最小单票权重。

最近，“选票价值差异”的数值成为了一个严重的社会问题。你的任务是尽可能地让这个值变小。

任务

给定 JOI 王国各省的信息以及代表人数，请确定如何将省份划分为选区，使得选票价值差异尽可能小。

输入格式

从标准输入读取以下数据。

• 输入的第一行包含四个以空格分隔的整数 $H, W, N, K$。其中，JOI 王国地图的高度为 $H$，宽度为 $W$，省份数量为 $N$，代表人数为 $K$。
• 接下来的 $H$ 行中，每行包含 $W$ 个以空格分隔的整数。在第 $i$ 行（$1 \le i \le H$）中，第 $j$ 个整数（$1 \le j \le W$）为 $S_{ij}$（$1 \le S_{ij} \le N$）。这表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子属于第 $S_{ij}$ 个省份。
• 在接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $P_i$，表示第 $i$ 个省份的选民人数。

输出格式

在 $N$ 行中输出将省份划分为选区的方式。输出的第 $i$ 行（$1 \le i \le N$）应包含一个整数，表示第 $i$ 个省份所属的选区编号。

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

1
2
1
3

提示

样例 1 解释

在此样例中，JOI 王国的形状如下图所示。

:::align{center} :::

各省的选民人数分别为 3、5、7、10。在该样例输出中，省份被划分为以下选区：

• 选区 1：省份 1 和省份 3
• 选区 2：省份 2
• 选区 3：省份 4

各选区的选民人数分别为 10、5、10。各选区的单票权重分别为 0.1、0.2、0.1。因此，选票价值差异为 $0.2 / 0.1 = 2$。如果 $X = 1.5$，$Y = 3$，则有 $\left(\frac{3 - 2}{3 - 1.5}\right)^2 \times 20 = 8.8\cdots$，该输出将获得 8 分。

对于此样例输入，以下划分是不允许的，因为选区 2 未能形成一个连通区域：

• 选区 1：省份 1
• 选区 2：省份 2 和省份 4
• 选区 3：省份 3

约束条件

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

• $1 \le H \le 200$
• $1 \le W \le 200$
• $1 \le N \le 10000$
• $1 \le K \le N$
• $1 \le P_i \le 100000$（$1 \le i \le N$）
• 对于每个省份，属于该省份的所有格子构成一个连通区域。

评分细则

对于每个输入文件，你的得分计算方式如下：

如果你的输出不满足题目描述中的条件，则得分为 0。如果满足条件，设 $D$ 为你输出方案的选票价值差异。那么你的得分按以下方式计算：

• 如果 $Y < D$，得分为 0。
• 如果 $X < D \le Y$，得分为 $\left(\frac{Y - D}{Y - X}\right)^2 \times 20$ 的值向下取整。
• 如果 $D \le X$，得分为 20。

$X, Y$ 的取值如下表所示：

翻译由 DeepSeek V3.2 完成