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/(\text{选区内的选民人数})$ 被称为该选区的单票权重。投票价值差异定义为所有选区中单票权重的最大值除以所有选区中单票权重的最小值。

最近，“投票价值差异”的值成为了一个严重的社会问题。你必须使该值尽可能小。

任务

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

输入格式

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

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

输出格式

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

数据范围

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

• $1 \le H \le 200$
• $1 \le W \le 200$
• $1 \le N \le 10\,000$
• $1 \le K \le N$
• $1 \le P_i \le 100\,000$（$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$ 的值如下表所示：

样例

样例输入 1

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

样例输出 1

1
2
1
3

说明

在这个例子中，JOI 王国的形状如下：

Province 1

Province 2 Province 3 Province 4

各省的选民人数分别为 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 \dots$，该输出得 8 分。

在该样例输入中，以下划分是不允许的，因为选区 2 没有形成一个连通区域：

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