#1209. SQUARE - Hình vuông

Cho bảng vuông kích thước . Các hàng được đánh số từ trên xuống dưới. Các cột được đánh số từ trái qua phải. Tại mỗi ô của bảng có thể là một ô cấm.

Yêu cầu: Cho vị trí ô trên bảng. Với mỗi ô, xác định hình vuông lớn nhất chứa ô đó và không chứa ô cấm.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa ký tự biểu thị dòng của bảng. Ký tự thứ biểu diễn ô . Giá trị # biểu diễn ô cấm;
• Dòng tiếp theo ghi số nguyên – số vị trí truy vấn;
• dòng tiếp, mỗi dòng chứa hai số nguyên xác định tọa độ ô truy vấn.

Dữ liệu ra:

• Ghi ra dòng, dòng thứ ghi tương ứng diện tích hình vuông lớn nhất tìm được, chứa ô trong truy vấn thứ .

Ví dụ:

Dữ liệu vào:

5 5
#...#
..#..
.....
#...#
#....
5
3 2
2 5
5 4
4 5
1 3

Dữ liệu ra:

9
4
9
0
1

Giới hạn:

Gọi là số ô cấm:

• số test tương ứng số điểm có ;
• số test khác tương ứng số điểm có ;
• số test khác tương ứng số điểm có ;
• số test còn lại tương ứng số điểm có .