Vương quốc JOI sắp tổ chức một cuộc bầu cử toàn quốc. Vương quốc gồm \(N\) tỉnh và được biểu diễn bằng một lưới hình chữ nhật có \(H\) hàng, \(W\) cột. Hai ô được coi là kề nhau nếu chúng có chung một cạnh ở bên trái, bên phải, phía trên hoặc phía dưới. Hai ô chỉ có chung một đỉnh không được coi là kề nhau.

\(H \times W\) ô được chia thành \(N\) tỉnh. Các ô của mỗi tỉnh tạo thành một vùng liên thông: có thể đi từ một ô bất kỳ đến mọi ô khác của tỉnh bằng cách đi qua các ô kề nhau cùng thuộc tỉnh đó. Tỉnh thứ \(i\) có \(P_i\) cử tri.

Bạn là chủ tịch ủy ban bầu cử của vương quốc JOI. Để bầu ra \(K\) đại biểu, bạn phải chia \(N\) tỉnh thành đúng \(K\) khu vực bầu cử, đánh số từ \(1\) đến \(K\). Mỗi tỉnh phải thuộc trọn vẹn một khu vực bầu cử. Mỗi khu vực phải chứa ít nhất một tỉnh, và tất cả các ô thuộc khu vực đó phải tạo thành một vùng liên thông theo cạnh.

Trọng số của một lá phiếu tại một khu vực bầu cử là nghịch đảo của tổng số cử tri trong khu vực đó. Độ chênh lệch giá trị lá phiếu là trọng số lớn nhất chia cho trọng số nhỏ nhất trong tất cả các khu vực bầu cử. Gần đây, độ chênh lệch này đã trở thành một vấn đề xã hội nghiêm trọng, vì vậy bạn muốn làm cho nó nhỏ nhất có thể.

Yêu cầu

Đây là bài chỉ nộp kết quả. Với mỗi bộ dữ liệu được cung cấp, hãy nộp một tệp mô tả cách chia các tỉnh thành các khu vực bầu cử sao cho độ chênh lệch giá trị lá phiếu nhỏ nhất có thể.

Dữ liệu vào

Có năm tệp dữ liệu: 01.txt, 02.txt, 03.txt, 04.txt và 05.txt. Mỗi tệp mô tả một bộ dữ liệu độc lập theo định dạng sau:

• Dòng đầu chứa bốn số nguyên \(H, W, N, K\) cách nhau bởi dấu cách, lần lượt là số hàng, số cột của bản đồ, số tỉnh và số đại biểu cần bầu.
• \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) số nguyên cách nhau bởi dấu cách. Số thứ \(j\) trên dòng thứ \(i\) là \(S_{i,j}\), cho biết ô ở hàng thứ \(i\) tính từ trên xuống và cột thứ \(j\) tính từ trái sang thuộc tỉnh \(S_{i,j}\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(P_i\), là số cử tri của tỉnh thứ \(i\).

Tất cả các bộ dữ liệu thỏa mãn:

• \(1 \le H \le 200\).
• \(1 \le W \le 200\).
• \(1 \le N \le 10\,000\).
• \(1 \le K \le N\).
• \(1 \le S_{i,j} \le N\) với \(1 \le i \le H\), \(1 \le j \le W\).
• \(1 \le P_i \le 100\,000\) với \(1 \le i \le N\).
• Các ô thuộc mỗi tỉnh tạo thành một vùng liên thông.

Dữ liệu ra

Với mỗi tệp dữ liệu 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, nộp một tệp kết quả tương ứng gồm đúng \(N\) dòng. Dòng thứ \(i\) chứa một số nguyên \(E_i\), là số hiệu khu vực bầu cử mà tỉnh thứ \(i\) thuộc về.

Một kết quả hợp lệ phải thỏa mãn \(1 \le E_i \le K\) với mọi \(i\), mỗi số hiệu từ \(1\) đến \(K\) phải xuất hiện ít nhất một lần, và các ô thuộc những tỉnh có cùng số hiệu khu vực bầu cử phải tạo thành một vùng liên thông theo cạnh.

Chấm điểm

Điểm được tính riêng cho từng bộ dữ liệu. Nếu tệp kết quả không thỏa mãn các điều kiện của bài toán, điểm của bộ dữ liệu đó bằng \(0\).

Với một kết quả hợp lệ, gọi \(D\) là độ chênh lệch giá trị lá phiếu của cách phân chia đã nộp. Điểm của bộ dữ liệu là:

Ký hiệu \(\lfloor x \rfloor\) là phần nguyên thu được khi bỏ phần thập phân của giá trị không âm \(x\). Các ngưỡng \(X, Y\) của từng bộ dữ liệu như sau:

Minh họa

Xét bộ dữ liệu sau:

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

Bản đồ có hai hàng và ba cột. Cả ba ô ở hàng trên thuộc tỉnh \(1\); ba ô ở hàng dưới lần lượt thuộc các tỉnh \(2, 3, 4\) từ trái sang phải. Số cử tri của bốn tỉnh lần lượt là \(3, 5, 7, 10\).

Một tệp kết quả hợp lệ cho bộ dữ liệu này là:

1
2
1
3

Cách phân chia này gồm:

• Khu vực bầu cử \(1\): tỉnh \(1\) và tỉnh \(3\).
• Khu vực bầu cử \(2\): tỉnh \(2\).
• Khu vực bầu cử \(3\): tỉnh \(4\).

Số cử tri của ba khu vực lần lượt là \(10, 5, 10\), nên trọng số của một lá phiếu lần lượt là \(0.1, 0.2, 0.1\). Do đó, độ chênh lệch giá trị lá phiếu là \(D = 0.2/0.1 = 2\). Nếu các ngưỡng của bộ dữ liệu này là \(X = 1.5\) và \(Y = 3\) thì:

Vì vậy, tệp kết quả này được \(8\) điểm.

Cách phân chia dưới đây không hợp lệ:

• Khu vực bầu cử \(1\): tỉnh \(1\).
• Khu vực bầu cử \(2\): tỉnh \(2\) và tỉnh \(4\).
• Khu vực bầu cử \(3\): tỉnh \(3\).

Lý do là các ô của khu vực bầu cử \(2\) không tạo thành một vùng liên thông.