Phần thưởng

Hiếu là người thắng cuộc trong một cuộc thi "Tìm hiểu kiến thức vũ trụ" và được nhận các phần thưởng do trung tâm TAS tài trợ. Các phần thưởng được bố trí trên một bảng 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à có giá trị là $a_{i,j}$ ($1\le i\le m$, $1\le j\le n$).

Để nhận phần thưởng, Hiếu cần trả lời các câu hỏi có dạng: "Cho một hình chữ nhật con có ô trái trên là ô $(x,y)$ và ô phải dưới là ô $(u,v)$, cần đưa ra tổng giá trị các phần quà trong hình chữ nhật con này", tức là tổng các $a_{i,j}$ với $x\le i\le u$ và $y\le j\le v$.

Yêu cầu: Cho giá trị các phần quà được đặt trên bảng và $q$ bộ $x_k,y_k,u_k,v_k$ ($k=1,2,\dots ,q$) tương ứng với $q$ truy vấn, hãy đưa ra các câu trả lời cho $q$ truy vấn.

Dữ liệu vào

• Dòng thứ nhất chứa ba số nguyên dương $m,n,q$ ($q\le m\times n$);
• Dòng thứ $i$ trong số $m$ dòng tiếp theo chứa $n$ số nguyên không âm, số thứ $j$ là $a_{i,j}$ ($a_{i,j}\le {10}^6$);
• Dòng thứ $k$ trong số $q$ dòng tiếp theo chứa $4$ số nguyên dương $x_k,y_k,u_k,v_k$ ($x_k\le u_k\le m$, $y_k\le v_k\le n$).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra

Gồm $q$ dòng, mỗi dòng chứa một số là câu trả lời cho một truy vấn theo thứ tự xuất hiện trong dữ liệu vào.

Ràng buộc

• $1\le m,n$; $m\times n\le {10}^6$.
• $1\le q\le m\times n$.
• $0\le a_{i,j}\le {10}^6$.
• $1\le x_k\le u_k\le m$, $1\le y_k\le v_k\le n$.

Subtasks

• Có $25\%$ số test ứng với $25\%$ số điểm của bài có $m,n\le 50$;
• Có $25\%$ số test khác ứng với $25\%$ số điểm của bài có $m=1$, $n\le {10}^6$;
• Có $25\%$ số test khác ứng với $25\%$ số điểm của bài có $m,n\le 1000$;
• Có $25\%$ số test còn lại ứng với $25\%$ số điểm của bài có $m\times n\le {10}^6$.

Ví dụ