Một nhóm bạn trẻ, trong đó có An, tham gia vào một thử thách mang tên "Thám hiểm mê cung cổ đại". Người chơi được đưa vào một mê cung hình chữ nhật khổng lồ, nơi mỗi bước đi đều có thể quyết định thắng bại.

Mê cung được cấu tạo như một lưới gồm ~n~ hàng, ~m~ cột. Mỗi ô trong mê cung mang một trạng thái:

• "." - khoảng trống, có thể di chuyển

• "#" - vật cản, không thể đi qua

Từ một ô, người chơi có thể di chuyển sang ~4~ hướng (trên, dưới, trái, phải), mỗi bước tốn ~1~ giây, miễn là không đâm vào tường đá hay bước ra ngoài mê cung.

Nhưng điều khiến mê cung này trở nên đặc biệt chính là những cánh cổng ma thuật. Rải rác trong mê cung là ~k~ cặp cổng dịch chuyển, mỗi cặp kết nối hai vị trí bất kỳ. Khi đứng trên một cánh cổng thứ ~i~ ~(1 \le i \le k)~ kết nối hai ô ~(a_i, b_i)~ và ô ~(c_i, d_i)~ (hai ô này có thể không kề cạnh), người chơi có thể lựa chọn dịch chuyển đến ô còn lại, tốn ~w_i~ giây. Tất cả mọi cánh cổng ma thuật đều kết nối hai ô trống.

Ban đầu, mục tiêu của trò chơi rất đơn giản: Ai đến được đích nhanh nhất sẽ chiến thắng.

Nhưng An nhanh chóng nhận ra mê cung này không hề đơn giản như một trò chơi. Cấu trúc của nó thay đổi. Những con đường tưởng như ngắn nhất lại dẫn vào ngõ cụt. Và các cánh cổng có vẻ như đang tuân theo một quy luật bí ẩn nào đó.

Nhiệm vụ: Để chuẩn bị cho hành trình nguy hiểm phía trước, An quyết định phân tích mê cung. Với mỗi câu hỏi, hãy xác định: Thời gian ít nhất để di chuyển từ một ô đến một ô khác, có thể sử dụng cả di chuyển thông thường và cánh cổng ma thuật.

• Nếu tồn tại đường đi ~\rightarrow~ trả về thời gian ngắn nhất

• Nếu không thể đi ~\rightarrow~ trả về ~-1~

Input

• Dòng đầu gồm các số nguyên ~n, m, k, Q~ ~(1 \le n \le 10, 1 \le m \le 10^4, 1 \le k \le 10, 1 \le Q \le 10^5)~.

• ~n~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le n)~ là một xâu gồm ~m~ kí tự ('.', '#') biểu diễn hàng thứ ~i~ của ma trận ~A~.

• ~k~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le k)~ gồm năm số nguyên ~a_i, b_i, c_i, d_i, w_i~ ~(1 \le a_i, c_i \le n, 1 \le b_i, d_i \le m, 1 \le w_i \le 10^6)~.

• ~Q~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le Q)~ gồm bốn số nguyên ~x_i, y_i, u_i, v_i~ ~(1 \le x_i, u_i \le n, 1 \le y_i, v_i \le m)~ thể hiện truy vấn thứ ~i~.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ ghi một số nguyên là số giây ít nhất để di chuyển. Nếu không tồn tại cách di chuyển từ ô ~(x_i, y_i)~ đến ô ~(u_i, v_i)~ thì dòng thứ ~i~ ghi ~-1~.

Scoring

Sample Input 1

5 9 1 2
###...###
#.......#
#...#####
#...#...#
#...#...#
2 3 5 7 15
2 2 5 4
2 2 5 6

Sample Output 1

5
17

Sample Input 2

1 12 0 2
..#......#..
1 2 1 5
1 4 1 9

Sample Output 2

-1
5