Vote-Value Disparity 1

Time limit1sMemory limit128 MB

Summary

Partition N connected provinces into K connected districts to minimize the ratio between the most and least powerful single vote.

Level: Hard8 of 10
Topics: Graph, Binary search, DFS
Solved: No attempts yet

Problem

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

The map is an $H \times W$ grid. Each cell connects to neighbors by sharing a side. The grid is partitioned into $N$ connected provinces. Province $i$ has $P_i$ voters.

You must divide the provinces into $K$ electoral districts to elect $K$ representatives. Each district contains at least one province, and the cells in a district form a connected region. Cells connect only through shared sides, not shared corners.

The weight of a single vote in a district is $1 / \text{(number of voters in that district)}$ . The vote-value disparity is the maximum such weight divided by the minimum. Minimize this disparity.

Input

The first line contains $H$ , $W$ , $N$ , and $K$ .

Each of the next $H$ lines has $W$ integers $S_{ij}$ , the province id of each cell.

Each of the next $N$ lines has $P_i$ , the number of voters in province $i$ .

Output

Print $N$ lines. Line $i$ is the district number ( $1$ to $K$ ) for province $i$ .

Constraints

$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$
Each province forms a connected region on the grid.

Examples1

Example 1
Input
```
2 3 4 3
1 1 1
2 3 4
3
5
7
10
```
Expected output
```
1
2
1
3
```