Thành phố IOI, nơi JOI sinh sống, nổi tiếng là rất nóng quanh năm.

Thành phố IOI có dạng hình chữ nhật được chia thành \(H\) hàng và \(W\) cột ô vuông. Mỗi ô là một tòa nhà, một bãi đất trống hoặc một bức tường. Có \(P\) ô là tòa nhà, được đánh số từ \(1\) đến \(P\).

JOI chỉ có thể đi vào các ô là tòa nhà hoặc bãi đất trống. Từ một ô, JOI chỉ có thể đi trực tiếp sang một ô kề cạnh, tức là có chung một cạnh với ô đó. Trong quá trình di chuyển, JOI không được đi ra ngoài thành phố IOI.

JOI cần đi bộ giữa các tòa nhà để giải quyết nhiều công việc khác nhau. Bên trong các tòa nhà có điều hòa, nhưng các bãi đất trống rất nóng vì nắng gắt, nên mỗi lần đi qua một ô đất trống, JOI cần uống \(1\) đơn vị nước. Hơn nữa, các bãi đất trống không có máy bán hàng tự động hay vòi nước uống, nên người dân thành phố IOI thường mang theo bình nước khi di chuyển. Một bình nước có dung tích \(x\) chứa được tối đa \(x\) đơn vị nước. Trong các ô tòa nhà có vòi nước, vì vậy JOI có thể đổ đầy lại bình nước.

Bình nước lớn rất bất tiện khi mang theo, nên JOI muốn dùng bình nhỏ nhất có thể. Với một số chuyến đi giữa các tòa nhà, hãy viết chương trình tìm dung tích bình nước nhỏ nhất mà JOI cần để thực hiện chuyến đi đó.

Yêu cầu

Cho bản đồ thành phố IOI và \(Q\) câu hỏi. Câu hỏi thứ \(i\) (\(1 \le i \le Q\)) là: “Dung tích bình nước nhỏ nhất cần có để di chuyển giữa tòa nhà \(S_i\) và tòa nhà \(T_i\) là bao nhiêu?”. Hãy viết chương trình trả lời từng câu hỏi.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa bốn số nguyên \(H, W, P, Q\), cách nhau bởi dấu cách. Thành phố IOI có \(H\) hàng và \(W\) cột ô vuông, trong đó có \(P\) ô tòa nhà; chương trình cần trả lời \(Q\) câu hỏi.
• \(H\) dòng tiếp theo mô tả bản đồ thành phố IOI. Dòng thứ \(r\) trong số này (\(1 \le r \le H\)) chứa một xâu gồm \(W\) ký tự, mỗi ký tự là . hoặc #. Ký tự thứ \(c\) (\(1 \le c \le W\)) mô tả ô ở hàng thứ \(r\) từ trên xuống và cột thứ \(c\) từ trái sang. Ký tự . biểu thị tòa nhà hoặc bãi đất trống; ký tự # biểu thị tường.
• \(P\) dòng tiếp theo mô tả vị trí các tòa nhà. Dòng thứ \(j\) trong số này (\(1 \le j \le P\)) chứa hai số nguyên \(A_j, B_j\), cách nhau bởi dấu cách, cho biết tòa nhà \(j\) nằm ở hàng thứ \(A_j\) từ trên xuống và cột thứ \(B_j\) từ trái sang. Ô tương ứng trên bản đồ đã cho được bảo đảm là ..
• \(Q\) dòng tiếp theo mô tả các câu hỏi. Dòng thứ \(i\) trong số này (\(1 \le i \le Q\)) chứa hai số nguyên \(S_i, T_i\), cách nhau bởi dấu cách, cho biết câu hỏi thứ \(i\) yêu cầu tìm dung tích bình nước nhỏ nhất cần có để di chuyển giữa tòa nhà \(S_i\) và tòa nhà \(T_i\).

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(i\) (\(1 \le i \le Q\)) chứa một số nguyên là dung tích bình nước nhỏ nhất cần có để di chuyển giữa tòa nhà \(S_i\) và tòa nhà \(T_i\). Nếu không thể di chuyển giữa hai tòa nhà, in -1. Nếu có thể di chuyển mà không đi qua ô đất trống nào, in 0.

Ràng buộc

Tất cả dữ liệu đầu vào thỏa mãn:

• \(1 \le H \le 2\,000\).
• \(1 \le W \le 2\,000\).
• \(2 \le P \le 200\,000\).
• \(1 \le Q \le 200\,000\).
• \(1 \le A_j \le H \quad (1 \le j \le P)\).
• \(1 \le B_j \le W \quad (1 \le j \le P)\).
• \((A_i, B_i) \ne (A_j, B_j) \quad (1 \le i < j \le P)\).
• \(1 \le S_i < T_i \le P \quad (1 \le i \le Q)\).

Phân nhóm

• Nhóm 1 (10 điểm): \(H \le 200\), \(W \le 200\), \(P \le 200\)
• Nhóm 2 (30 điểm): \(P \le 5\,000\), \(Q = 1\)
• Nhóm 3 (30 điểm): \(P \le 5\,000\), \(Q \le 10\,000\)
• Nhóm 4 (30 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

3
4
4
2

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

-1
7