BCHESS - Bàn cờ tướng

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua Codeforces (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên Codeforces. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên Codeforces

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 8x8, 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 9x9, 4 ô ở 4 góc màu đen) và loại 3 (kích thước 9x9, 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 NxN 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 <= 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.

Example

Input:
5
00101
11010
00101
01010
11101
Output:
4 1
3 3
3 2


  • Người up: yellowflash12
  • Nguồn bài: by winterwolf94