Giải bài trực tuyến

Tèo được các admin VNOI đố cho một trò chơi như sau :

• Tèo có một bảng hình chữ nhật N x M, mỗi ô có một màu nhất định và K lần tô màu.
• Trong mỗi lần tô màu, Tèo chọn một vùng có số hiệu màu như nhau và tô một màu khác. (Một vùng là một dãy các ô chung cạnh có cùng màu với nhau).

Ví dụ :

Ở hình bên trái nếu ta chọn ô (3,3) màu xanh lá và tô thành màu vàng thì sẽ thu được hình bên phải.

Sau khi biến đổi, bảng màu sẽ có Q vùng, mỗi vùng sẽ có c[i] ô (i=1->Q). Câu hỏi của các admin VNOI cho Tèo là : Hãy chỉ ra cách tô màu sau K lần sao cho c[1]^2 + .... + c[Q]^2 càng lớn càng tốt.

Dữ liệu

• Dòng đầu tiên chứa 3 số n, m, k. (n, m, k <= 50)
• n dòng tiếp theo, mỗi dòng chứa m số thể hiện màu được tô cho ô tương ứng trên bảng (mỗi màu khác nhau được đánh một số hiệu khác nhau và các ô có màu giống nhau thì được đánh cùng một số). Số hiệu màu là số tự nhiên không vượt quá 3000.

Kết quả

• Ghi ra trên k dòng, thể hiện các bước tô màu theo thứ tự tăng dần của thời gian, mỗi dòng có dạng: i, j, t tương ứng với việc tô màu t cho ô (i, j).

Ví dụ

Dữ liệu:

3 4 2

1 1 2 3

1 2 2 3

2 2 3 3

Kết quả:

3 3 2

1 1 2

Cách tính điểm

Điểm cho mỗi output hợp lệ sẽ tỷ lệ với tổng c[1]^2 + .... + c[Q]^2.