Từ lâu, Quý vẫn nghe kể về một chiếc đàn guitar điện cổ đại được cất giấu trong hệ thống mật thất nằm sâu bên dưới một công trình bị bỏ quên. Sau nhiều năm lần theo những manh mối rời rạc, Quý tìm được một tấm bản đồ mô tả cấu trúc của hệ thống này.

Theo tấm bản đồ, hệ thống mật thất là một mê cung cơ khí gồm ~n~ hàng và ~m~ cột. Mỗi ô là một căn phòng hình vuông. Trên bốn cạnh của một căn phòng có thể có hoặc không có tường, vì vậy có tổng cộng ~2^4 = 16~ loại phòng khác nhau.

Tuy nhiên, tấm bản đồ còn ghi lại một đặc điểm bất thường của mê cung: sau mỗi giây, tất cả các căn phòng đồng thời xoay ~90^\circ~ theo chiều kim đồng hồ. Vì thế, vị trí các bức tường và những lối đi giữa các căn phòng thay đổi liên tục theo thời gian.

Để lần theo dấu vết của chiếc đàn, Quý cần thực hiện nhiều cuộc khảo sát. Mỗi truy vấn đưa ra một ô bắt đầu ~S~ và một mật thất đích ~E~ mà Quý cần tới. Tại thời điểm ~t = 0~, mê cung ở đúng trạng thái được thể hiện trên bản đồ và Quý bắt đầu tại ~S~.

Trong mỗi giây, các sự kiện xảy ra theo đúng thứ tự sau:

1. Quý chọn đứng yên hoặc di chuyển sang một ô chung cạnh.
2. Nếu di chuyển, cạnh chung giữa hai ô phải hoàn toàn thông: phía tương ứng của cả hai căn phòng đều không có tường. Chỉ cần một trong hai phía có tường thì Quý không thể đi qua.
3. Sau khi hành động kết thúc, toàn bộ các căn phòng đồng thời xoay ~90^\circ~ theo chiều kim đồng hồ.

Việc xoay phòng không làm thay đổi vị trí của Quý khi đang đứng bên trong căn phòng đó. Nếu Quý đã tới ~E~ sau một hành động, cuộc khảo sát kết thúc ngay và không cần quan tâm tới lần xoay tiếp theo.

Với mỗi truy vấn, hãy tìm số giây ít nhất để Quý đi từ ~S~ tới đúng mật thất ~E~. Nếu không thể tới được ~E~, in ra -1.

Các truy vấn độc lập với nhau: trước mỗi cuộc khảo sát, mê cung luôn được đưa trở lại đúng trạng thái trên tấm bản đồ tại thời điểm ~t = 0~.

Mã hóa các căn phòng

Mỗi ký tự từ a đến p tương ứng với một loại phòng như hình dưới đây.

Cấu hình Input

• Dòng đầu tiên chứa ba số nguyên ~n, m, q~ ~(1 \leq n,m \leq 300,\ 1 \leq q \leq 10^5)~ lần lượt là số hàng, số cột của mê cung và số truy vấn.
• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu độ dài ~m~ chỉ gồm các ký tự từ a đến p. Ký tự thứ ~j~ của dòng thứ ~i~ mô tả căn phòng ~(i,j)~ tại thời điểm ~t = 0~.
• ~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~x_s, y_s, x_e, y_e~, biểu diễn một truy vấn với ô bắt đầu ~S=(x_s,y_s)~ và mật thất đích ~E=(x_e,y_e)~.
• Các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~m~ từ trái sang phải.
• Gọi ~A~ là số ô bắt đầu phân biệt và ~B~ là số ô kết thúc phân biệt xuất hiện trong các truy vấn. Dữ liệu bảo đảm ~A\cdot B \leq 10^5~.

Cấu hình Output

• Với mỗi truy vấn, in ra trên một dòng số giây ít nhất để Quý đi từ ~S~ tới ~E~.
• Nếu không thể tới được ~E~, in ra -1.

Sample Input 1

3 4 3
aaaa
aaaa
aaaa
1 1 3 4
2 2 2 2
3 1 1 4

Sample Output 1

5
0
5

Trong sample đầu tiên, tất cả các phòng đều là a, tức không có bức tường nào. Vì vậy việc xoay mê cung không làm thay đổi đường đi.

Sample Input 2

1 2 2
ca
1 1 1 2
1 2 1 1

Sample Output 2

2
2

Ở thời điểm ~t=0~, cạnh chung giữa hai phòng bị chặn. Quý có thể đứng yên trong giây đầu tiên; sau lần xoay đầu tiên, bức tường chuyển xuống cạnh dưới và cạnh chung được mở. Vì vậy cả hai truy vấn đều có đáp án bằng 2 .

Subtasks