Alice là người chiến thắng trong một cuộc thi "Tìm hiểu kiến thức vũ trụ" và được nhận phần thưởng theo cách sau:

Các phần thưởng được bố trí trên một bảng có kích thước \(m \times n\). Các dòng của bảng được đánh số từ \(1\) đến \(m\), từ trên xuống dưới và các cột của bảng được đánh số từ \(1\) đến \(n\), từ trái qua phải. Ô nằm trên giao của dòng \(i\) và cột \(j\) được gọi là ô \((i, j)\) và trên ô đó chứa một món quà loại \(a_{i,j}\). Giữa \(2\) ô \((x, y)\) và \((u, v)\) bất kì chứa cùng một loại quà, luôn tồn tại một đường đi qua các ô chung cạnh cũng chứa loại quà đó.

Đề nhận phần thưởng, Alice cần trả lời truy vấn: "Có bao nhiêu loại quà khác nhau gồm các ô được giới hạn bởi hình chữ nhật có góc trái trên ở ô \((x_{1}, y_{1})\) và góc phải dưới ở ô \((x_{2}, x_{2})\)?".

Có \(q\) truy vấn như vậy, Alice cần trả lời được tất cả các câu hỏi để nhận thưởng. Hãy giúp Alice trả lời các truy vấn này.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(m, n\) \((1 \leq m, n \leq 1000)\) là kích thước của bảng.
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên dương. Số thứ \(j\) là \(a_{i,j}\) \((1 \leq a_{i,j} \leq 10^{6})\).
• Dòng tiếp theo chứa số \(q\) \((1 \leq q \leq 50000)\) là số truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng ghi một truy vấn gồm \(4\) số nguyên dương \(x_{1}, y_{1},x_{2}, y_{2}\) \((1 \leq x_{1} \leq x_{2} \leq m, 1 \leq y_{1} \leq y_{2} \leq n)\).

Output

• Với mỗi truy vấn, in ra trên một dòng là kết quả tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(1 \leq m, n, q \leq 200\).
• Subtask \(2\) (\(25\%\) số điểm): \(1 \leq m, n \leq 90\).
• Subtask \(3\) (\(25\%\) số điểm): \(1 \leq a_{i, j} \leq 20\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc nào thêm.

Example

4 4
1 2 2 3
1 2 4 5
1 2 4 4
1 2 2 4
4
2 3 2 3
2 4 3 4
1 2 1 4
4 1 4 3

1
2
2
2