Vote-Value Disparity 4

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 grid of H × W blocks. There are H blocks in the vertical direction and W blocks in the horizontal direction. A block is connected to another block that shares one of its four sides (left, right, top, bottom). The H × W blocks are divided into N provinces. Each province is a connected region of blocks. The i-th province (1 ≤ i ≤ N) has Pi voters in total.

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

For each electoral district, the value 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 as the maximal weight of a single vote over all electoral districts divided by the minimal weight of a single vote over all electoral districts.

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

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

Read the following data from the standard input.

• The first line contains four space-separated integers H, W, N, K, where H is the height of the map of the JOI kingdom, W is the width, N is the number of provinces, and K is the number of representatives.
• Each of the following H lines contains W space-separated integers. The j-th integer in the i-th line (1 ≤ i ≤ H, 1 ≤ j ≤ W) is Sij (1 ≤ Sij ≤ N). This means the block in the i-th row from the top and the j-th column from the left belongs to the Sij-th province.
• The i-th line (1 ≤ i ≤ N) of the following N lines contains an integer Pi, the number of voters in the i-th province.

Write the way to divide the provinces into electoral districts in N lines. The i-th line (1 ≤ i ≤ N) of the output must contain the number of the electoral district to which the i-th province belongs.

• 1 ≤ H ≤ 200
• 1 ≤ W ≤ 200
• 1 ≤ N ≤ 10 000
• 1 ≤ K ≤ N
• 1 ≤ Pi ≤ 100 000 (1 ≤ i ≤ N)
• For each province, the blocks belonging to the province form a connected region.

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

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 and Y = 3, we have ((3−2)/(3−1.5))2 × 100 = 44.4444444444···, and this output is worth 44.4444444444··· points.

In this sample input, the following division is not allowed because 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