투표 가치 편차 1

JOI 왕국에서 총선이 열린다. 왕국은 $N$개의 주로 이루어져 있다.

지도는 $H \times W$ 격자로 표현된다. 세로 $H$칸, 가로 $W$칸이다. 각 칸은 상하좌우로 인접한 칸과 연결된다. $H \times W$개의 칸은 $N$개의 주로 나뉜다. 각 주는 연결된 영역이다. $i$번째 주에는 총 $P_i$명의 유권자가 있다.

선거관리위원회 위원장인 당신은 $N$개의 주를 $K$개의 선거구로 나누어 $K$명의 의원을 선출해야 한다. 각 선거구는 최소 한 주를 포함하고, 선거구에 속한 칸들은 연결된 영역을 이룬다. 칸은 상하좌우로만 연결되며, 꼭짓점만 맞닿는 경우는 연결되지 않는다.

선거구의 1표 가치는 $1 / \text{(해당 선거구 유권자 수)}$이다. 투표 가치 편차는 모든 선거구의 1표 가치 중 최댓값을 최솟값으로 나눈 값이다. 이 값을 가능한 한 작게 만들도록 선거구를 나눈다.

첫 줄에 $H$, $W$, $N$, $K$가 공백으로 구분되어 주어진다.

다음 $H$줄에는 각 줄에 $W$개의 정수 $S_{ij}$가 주어진다. $i$번째 줄 $j$번째 수는 위에서 $i$번째, 왼쪽에서 $j$번째 칸이 속한 주 번호이다 ($1 \le S_{ij} \le N$).

다음 $N$줄에는 각 줄에 $P_i$, $i$번째 주의 유권자 수가 주어진다.

$N$줄을 출력한다. $i$번째 줄에는 $i$번째 주가 속한 선거구 번호 ($1$부터 $K$까지의 정수)를 출력한다.

• $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$
• 각 주에 속한 칸들은 연결된 영역을 이룬다.