표 가치 격차 3

JOI 왕국에서 국회의원 선거가 열린다. JOI 왕국은 N개의 주로 이루어져 있다.

JOI 왕국의 지도는 H × W개의 칸으로 이루어진 직사각형 모양의 격자이다. 세로 방향으로 H개의 칸이 있고, 가로 방향으로 W개의 칸이 있다. 어떤 칸은 자신의 네 변(왼쪽, 오른쪽, 위, 아래) 중 하나를 통해 다른 칸과 연결된다. H × W개의 칸은 N개의 주로 나뉜다. 각 주는 칸들로 이루어진 연결된 영역이다. i번째 주에는 총 Pi명의 유권자가 있다 (1 ≤ i ≤ N).

당신은 JOI 중앙선거관리위원회의 위원장이다. 당신의 임무는 N개의 주를 K개의 선거구로 나누어 K명의 대표를 선출하는 것이다 (1 ≤ K ≤ N). 각 선거구는 적어도 하나의 주를 포함해야 하며, 한 선거구에 속한 칸들은 연결된 영역을 이루어야 한다. 어떤 칸은 자신의 네 변(왼쪽, 오른쪽, 위, 아래) 중 하나를 통해 다른 칸과 연결된다. 꼭짓점만 공유하는 두 칸은 연결되지 않은 것이다.

각 선거구에 대해 1/(선거구의 유권자 수)를 그 선거구의 한 표의 무게라고 한다. 표 가치 격차는 모든 선거구의 한 표의 무게 중 최댓값을 최솟값으로 나눈 값으로 정의한다.

최근 들어 "표 가치 격차"가 심각한 사회 문제가 되고 있다. 당신은 이 값을 가능한 한 작게 만들어야 한다.

JOI 왕국의 주 정보와 대표의 수가 주어졌을 때, 표 가치 격차가 가능한 한 작아지도록 주를 선거구로 나누는 방법을 구하라.

표준 입력에서 다음 데이터를 읽는다.

• 첫 번째 줄에는 H, W, N, K가 공백으로 구분되어 주어진다. H는 JOI 왕국 지도의 높이, W는 너비, N은 주의 수, K는 대표의 수이다.
• 다음 H개의 줄 각각에는 W개의 정수가 공백으로 구분되어 주어진다. i번째 줄 (1 ≤ i ≤ H)의 j번째 정수 (1 ≤ j ≤ W)는 Sij이다 (1 ≤ Sij ≤ N). 이는 위에서 i번째 행, 왼쪽에서 j번째 열에 있는 칸이 Sij번째 주에 속한다는 뜻이다.
• 다음 N개의 줄의 i번째 줄 (1 ≤ i ≤ N)에는 i번째 주의 유권자 수 Pi가 주어진다.

주를 선거구로 나누는 방법을 N개의 줄에 출력한다. 출력의 i번째 줄 (1 ≤ i ≤ N)에는 i번째 주가 속하는 선거구의 번호를 출력한다.

• 1 ≤ H ≤ 200
• 1 ≤ W ≤ 200
• 1 ≤ N ≤ 10 000
• 1 ≤ K ≤ N
• 1 ≤ Pi ≤ 100 000 (1 ≤ i ≤ N)
• 각 주에 속한 칸들은 연결된 영역을 이룬다.

이 예에서 JOI 왕국의 모양은 다음과 같다.

각 주의 유권자 수는 각각 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이라면 ((3−2)/(3−1.5))2 × 100 = 44.4444444444···이고, 이 출력은 44.4444444444···점을 받는다.

이 예의 입력에서 다음 분할은 선거구 2가 연결된 영역을 이루지 않으므로 허용되지 않는다.

• 선거구 1 : 주 1
• 선거구 2 : 주 2와 주 4
• 선거구 3 : 주 3