Description

This is an Output-only task.

A national election will be held in the JOI kingdom. The JOI kingdom consists of $N$ provinces.

The map of the JOI kingdom is a rectangular-shaped grid consisting of $H \times W$ blocks. There are $H$ blocks in the vertical direction, and there are $W$ blocks in the horizontal direction. A block is connected with another block by one of the four sides (left, right, top, bottom) of it. The $H \times W$ blocks are divided into $N$ provinces. Each province is a connected region consisting of blocks. In total, there are $P_i$ voters in the $i$-th province ($1 \le i \le N$).

You are the chairman of the National Election Committee of JOI. Your task is to divide the $N$ provinces into $K$ electoral districts ($1 \le K \le N$) in order to elect $K$ representatives. Each electoral district should contain at least one province, and the blocks belonging to an electoral district should form a connected region. Note that a block is connected with another block by one of the four sides (left, right, top, bottom). Two blocks sharing only a vertex are not connected.

For each electoral district, the ratio $1 /$ (the number of voters in the electoral district) is called the weight of a single vote of the electoral district. The vote-value disparity is defined to be the maximal weight of a single vote for all electoral districts divided by the the minimal weight of a single vote for all electoral districts.

Recently, the value of "the vote-value disparity" becomes a serious social issue. You have to make this value as small as possible.

Task

Given the information of the provinces of the JOI kingdom and the number of representatives, determine how to divide the provinces into electoral districts so that the value of the vote-value disparity is as small as possible.

Input Format

Read the following data from the standard input.

• The first line of input contains four space separated integers $H, W, N, K$, where the height of the map of the JOI kingdom is $H$, the width is $W$, the number of provinces is $N$, the number of representatives is $K$.
• Each of the following $H$ lines contains $W$ space separated integers. In the $i$-th line ($1 \le i \le H$), the $j$-th integer ($1 \le j \le W$) is $S_{ij}$ ($1 \le S_{ij} \le N$). This means the block in $i$-th row from above and the $j$-th column from left belongs to the $S_{ij}$-th province.
• In the $i$-th line ($1 \le i \le N$) of the following $N$ lines contains an integer $P_i$, the number of voters in the $i$-th province.

Output Format

Write the way to divide the provinces into electoral districts in $N$ lines. The $i$-th line ($1 \le i \le N$) of output should contain an integer, the number of the electoral district where the $i$-th province belongs.

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

1
2
1
3

Hint

Sample 1 Explanation

In this example, the shape of the JOI kingdom is as follows.

:::align{center} :::

The number of voters in each province is 3, 5, 7, 10, respectively. In this sample output, the provinces are divided into electoral districts as follows.

• Electoral District 1: Province 1 and Province 3
• Electoral District 2: Province 2
• Electoral District 3: Province 4

The number of voters in each electoral district is 10, 5, 10, respectively. The weight of a single vote for each electoral district is 0.1, 0.2, 0.1, respectively. Therefore, the vote-value disparity is $0.2 / 0.1 = 2$. If $X = 1.5$, $Y = 3$, we have $\left(\frac{3 - 2}{3 - 1.5}\right)^2 \times 20 = 8.8\cdots$ and this output is worth 8 points.

In this sample input, the following division is not allowed because the Electoral District 2 does not form a connected region.

• Electoral District 1: Province 1
• Electoral District 2: Province 2 and Province 4
• Electoral District 3: Province 3

Constraints

All input data satisfy the following conditions.

• $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$)
• For each province, the blocks belonging to the province form a connected region.

Grading

For each input, your score is calculated as follows.

If your output does not satisfy the condition in the task statement, your score is 0. If it satisfies the condition, let $D$ denote the vote-value disparity of your output. Then your score is calculated by the following way.

• If $Y < D$, your score is 0.
• If $X < D \le Y$, your score is the value of $\left(\frac{Y - D}{Y - X}\right)^2 \times 20$ truncated to zero decimal places.
• If $D \le X$, your score is 20.

The values of $X, Y$ are given in the following table.