Như mọi người đã biết (hoặc sắp được biết), nhà hát lớn thành phố Hồ Chí Minh là một nhà hát rất đẹp theo lối kiến trúc Đế Quốc, một nơi mà khi đặt chân đến TP Hồ Chí Minh thì ai cũng nên đến tham quan thử một lần cho biết.

Nhà hát có ~m~ dãy ghế, được đánh số từ ~1~ đến ~m~, dãy ghế ~1~ gần sân khấu nhất, dãy ghế ~m~ xa sân khấu nhất, mỗi dãy ghế có đúng ~n~ cái ghế được đánh số từ ~1~ đến ~n~ từ trái sang. Theo khảo sát của ban điều hành nhà hát thì mỗi ghế trong nhà hát có một độ ưa chuộng khác nhau, ghế ở hàng ~i~, cột ~j~ có một giá trị ưa chuộng là số nguyên ~p_{i, j}~.

Ngày mai sắp có một chương trình biểu diễn hay, nhân dịp đó, các đoàn du khách tham quan TP Hồ Chí Minh muốn đến đặt chổ để xem biểu diễn. Do số lượng khách tham quan của mỗi đoàn khác nhau và để cho nhiều đoàn có thể xem được biểu diễn, ban điều hành nhà hát đã quyết định mỗi đoàn tham quan khi đến đặt chổ sẽ phải đặt các ghế trong một hình vuông dxd, không hơn không kém (tức là có ~d~ hàng ghế, mỗi hàng có ~d~ cái ghế).

Do đó, khi một trưởng đoàn đến để đặt chổ cho đoàn của mình, họ sẽ chọn trong các ghế còn trống (chưa được các đoàn trước đặt), một hình vuông dxd có góc trái trên là ~(x_0~, y0) ~-~ (hàng ~x_0~, cột ~y_0)~ sao cho tích 'giá trị ưa chuộng' của các ghế trong hình vuông đó là lớn nhất (tức là tích các ~p_{i, j}~, với ~x_0 \leq i < x_0 + d~; ~y_0 \leq j < y_0 + d)~, nếu có nhiều hình vuông thỏa mãn, họ sẽ chọn hình vuông có ~x_0~ nhỏ nhất, nếu vẫn còn nhiều hình vuông thỏa mãn, họ sẽ chọn hình vuông có ~y_0~ nhỏ nhất, sau khi chọn được rồi thì họ sẽ đặt toàn bộ ghế trong hình vuông đó.

Biết rằng số lượng đoàn tham quan đến đặt chổ cho đoàn mình là rất nhiều nên khi nào vẫn còn cách chọn một hình vuông dxd các ghế trống thì vẫn sẽ có đoàn đến để đặt chổ theo cách chọn đã nêu trên.

Yêu cầu: Hãy giúp ban điều hành nhà hát tính trước xem sẽ có tối đa bao nhiêu đoàn đến để đặt chổ cho đoàn của mình và vị trí mà các đoàn tham quan đã đặt chổ

Input

• Dòng đầu tiên là ~3~ số nguyên ~m~, ~n~, ~d~ ~(1 \leq d \leq~ ~min(m~, ~n)~).
• ~m~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên, số thứ ~j~ ở dòng ~i~ là ~p_{i, j}~.

Output

• Dòng đầu tiên chứa số ~K~, là số lượng đoàn tham quan nhiều nhất có thể đến đặt chổ tại nhà hát.
• ~K~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên ~x_0~, ~y_0~ là tọa độ góc trái trên của hình vuông mà đoàn thứ ~i~ đến đặt chổ theo thứ tự thời gian (đoàn thứ ~1~ là đoàn đầu tiên đến đặt chổ, đoàn thứ ~2~ là đoàn kế tiếp, ...).

Giới hạn

• ~20\%~ test đầu có ~1 \leq m~, ~n \leq 5~, ~0 < p_{i, j} \leq 3~
• ~20\%~ test kế tiếp có ~1 \leq m~, ~n \leq 50~, 0 ~< p_{i, j} \leq 3~
• ~20\%~ test kế tiếp có ~1 \leq m~, ~n \leq 50~, ~0 < p_{i, j} \leq 10^{9}~
• ~20\%~ test kế tiếp có ~1 \leq m~, ~n \leq 500~, ~0 < p_{i, j} \leq 1000~
• ~20\%~ test còn lại có ~1 \leq m~, ~n \leq 500~, ~0 < p_{i, j} \leq 10^{9}~

Sample Input 1

4 4 3
1 2 3 5
7 8 1 6
9 8 7 3
2 4 1 4

Sample Output 1

1
1 2

Sample Input 2

4 4 2
1 1 1 1
2 2 1 1
2 2 1 1
2 2 2 2

Sample Output 2

3
2 1
3 3
1 3

Note

- Giải thích ví dụ 1: Hình vuông ~3 \times 3~ có tích 'giá trị ưa chuộng' lớn nhất có góc trái trên ở ô ~(1~, ~2)~, có giá trị ~2 \times 3 \times 5 \times 8 \times 1 \times 6 \times 8 \times 7 \times 3 = 241920~. Sau khi đoàn đầu đặt ghế xong thì không còn đủ ghế trống để tiếp tục đặt ghế thỏa mãn hình vuông ~3 \times 3~ nữa).

- Giải thích ví dụ 2: Khi đoàn đầu tiên đến đặt chổ, có ~2~ vị trí hình vuông có cùng giá trị lớn nhất, đó là hình vuông góc trái trên là ~(2~, ~1)~ và ~(3~, ~1)~. Do đó trưởng đoàn sẽ ưu tiên đặt ghế trong hình vuông có góc trái trên ở vị trí ~(2~, ~1)~. ~2~ đoàn tiếp theo sẽ lần lượt đặt ghế theo giá trị lớn nhất, có vị trí góc trái trên là ~(3~, ~3)~ rồi ~(1~, ~3)~).