Bàn cờ tướng


Submit solution

Points: 0.54 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem type

Năm \(2020\), cờ vua là môn thể thao trí tuệ phổ biến nhất trên toàn thế giới, vượt xa cờ tướng. Ở trường chuyên \(X\), ban giám hiệu muốn học sinh rèn luyện trí óc ngay cả trong giờ thể dục nên đã thay tất cả các môn bóng đá, cầu lông, bóng bàn, ...bằng cờ vua. Đăng rất thích đánh cờ vua nên điều này làm cậu hào hứng.

Một bàn cờ vua là một bảng ô vuông mà trên mỗi hàng, mỗi cột các ô màu đen và trắng nằm xen kẽ nhau. Trên thị trường, ngoài bàn cờ vua truyền thống loại 1(kích thước \(8 \times 8\), \(2\) ô ở \(2\) góc đối diện có màu giống nhau) còn có bán \(2\) loại bàn cờ vua mới: loại \(2\) (kích thước \(9 \times 9\), \(4\) ô ở \(4\) góc màu đen) và loại \(3\) (kích thước \(9 \times 9\), \(4\) ô ở \(4\) góc màu trắng).

Trong một lần làm bài tập tin học, Đăng bắt gặp một bảng kích thước \(N \times N\) chỉ gồm các ô có giá trị \(0\) và \(1\). Xem như các ô \(0\) có màu trắng và các ô \(1\) có màu đen. Ta định nghĩa một hình vuông loại \(A\) là hình vuông có tính chất giống bàn cờ loại \(A\) (ở đây chỉ quan tâm đến tính xen kẽ màu của các ô liên tiếp và màu của \(4\) ô ở \(4\) góc chứ không tính đến kích thước). Một ô '1' được xem như một hình vuông loại \(2\) và một ô '0' được xem như một hình vuông loại \(3\).

Gọi \(S_{A}\) là độ dài cạnh của hình vuông loại A lớn nhất và \(T_{A}\) là số lượng hình vuông loại A có độ dài cạnh bằng \(S_{A}\) .Đăng muốn biết giá trị của các \(S_{i}\) và \(T_{i}\) .

Input

Dòng đầu là số nguyên dương \(N\) (\(N \le 2000\)). \(N\) dòng tiếp theo, mỗi dòng gồm \(N\) kí tự là '0'hoặc '1'

Output

Gồm 3 dòng, trên dòng thứ \(i\) ghi 2 số nguyên \(S_{i}\) và \(T_{i}\).

Nếu không tồn tại hình vuông loại A thì xem như \(S_{A} =T_{A}\) =0.

Sample Input

5
00101
11010
00101
01010
11101

Sample Output

4 1
3 3
3 2

Comments

There are no comments at the moment.