Tổng hình chữ nhật

Cho ma trận số nguyên \(a\) kích thước \(n \times m\).

Bạn cần xử lý \(q\) truy vấn. Mỗi truy vấn yêu cầu tính tổng các phần tử nằm trong hình chữ nhật có góc trên bên trái là \((x_1, y_1)\) và góc dưới bên phải là \((x_2, y_2)\).

Input

• Dòng đầu chứa ba số nguyên \(n\), \(m\), \(q\) \((1 \le n, m \le 1000,\ 1 \le q \le 10^5)\).
• \(n\) dòng tiếp theo, mỗi dòng \(m\) số nguyên \(a_{i,j}\) \((|a_{i,j}| \le 10^4)\).
• \(q\) dòng tiếp theo, mỗi dòng gồm bốn số nguyên \(x_1, y_1, x_2, y_2\) \((1 \le x_1 \le x_2 \le n,\ 1 \le y_1 \le y_2 \le m)\).

Output

In ra \(q\) dòng, mỗi dòng ghi kết quả của một truy vấn.

Scoring

• Subtask 1 (50%): \(n, m, q \le 100\)
• Subtask 2 (50%): Không có ràng buộc thêm.

Sample Input 1

3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3

Sample Output 1

12
28