Cho bản đồ một vùng đất có thể coi là một bảng chữ nhật với kích thước ~m \times n~; các hàng đánh số từ ~1~ đến ~m~ theo thứ tự từ Bắc tới Nam, các cột được đánh số từ ~1~ đến ~n~ theo thứ tự từ Đông sang tây. Lô đất nằm trên hàng ~i~ và cột ~j~ được kí hiệu là ô ~(i, j)~; trên mỗi ô ghi một chữ cái thuộc một trong bốn kí tự {N, S, E, W} với ý nghĩa: N là hướng Bắc, S là hướng Nam, E là hướng Đông, W là hướng Tây. Tại mỗi ô, có thể di chuyển sang các ô kề cạnh với nó, bước đi sẽ tính phí như sau:

• Nếu hướng di chuyển trùng với hướng ghi trên ô đó sẽ mất chi phí là ~1~

• Nếu hướng di chuyển vuông góc với hướng ghi trên ô thì chi phí là ~2~

• Nếu hướng di chuyển ngược hoàn toàn với hướng ghi trên ô thì chi phí là ~3~

Ví dụ: Hai đường đi sau lần lượt có chi phí là ~11~ và ~17~

• Bảng thứ nhất gồm các dòng NEESWE, WWWESS, SNWWWW. Đường đi qua các mốc ~(1, 1) \rightarrow (1, 5) \rightarrow (3, 5) \rightarrow (3, 3)~.

• Bảng thứ hai gồm các dòng SESWE, EESNW, NWEEN, EWSEN. Đường đi qua các mốc ~(1, 1) \rightarrow (1, 3) \rightarrow (3, 3) \rightarrow (3, 5) \rightarrow (4, 5) \rightarrow (4, 2)~.

Yêu cầu: Cho ~q~ câu hỏi với bốn số ~x, y, z, t~; với mỗi câu hỏi hãy tìm đường đi có chi phí nhỏ nhất bắt đầu từ ô ~(x, y)~ và kết thúc tại ô ~(z, t)~.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~m, n, q~ (~m, n \le 10^3; q \le 10~) cho biết kích thước của vùng đất và số câu hỏi

• ~m~ dòng tiếp, mỗi dòng chứa ~n~ kí tự mô tả chữ cái ghi trên mỗi ô đất

• ~q~ dòng tiếp, mỗi dòng chứa bốn số nguyên dương ~x, y, z, t~ (~x, z \le m; y, t \le n~)

Output

~q~ dòng, mỗi dòng là một số nguyên theo thứ tự là chi phí của đường đi tìm được trong các câu hỏi tương ứng.

Scoring

Sample Input 1

3 6 2
NEESWE
WWWESS
SNWWWW
1 1 3 6
1 5 3 3

Sample Output 1

9
5

Sample Input 2

4 5 3
SESWE
EESNW
NWEEN
EWSEN
1 3 3 1
1 5 2 4
3 2 1 4

Sample Output 2

6
3
6