B. BONUS - Phần thưởng

Bộ nhớ: 256 MiB Thời gian: 2000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Nguồn: Đề thi chính thức K10 và 11 DHBB 2015-2016

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 × 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_{ij}\ (1 ≤ i ≤ m, 1 ≤ j ≤ 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ên trái là ô (y,x) và ô dưới phải là ô (v,u) , cần đưa ra tổng giá trị các phần quà trong hình chữ nhật con này”.

Yêu cầu: Cho giá trị các phần quà được đặt trên bảng và q bộ y_k, x_k , v_k, u_k\ (k = 1, 2, ..., 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 ≤ m × n) ;
  • Dòng thứ i trong số m dòng tiếp theo chứa n số nguyên dương, số thứ j a_{ij}\ (a_{ij} ≤ 10^6) ;
  • Dòng thứ k trong số q dòng tiếp theo chứa 4 số nguyên dương y_k, x_k , v_k, u_k\ (k = 1, 2, \dots, q) .

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:

  • Ghi ra 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.

Ví dụ:

Dữ liệu vào:
4 2 2
2 2
3 0
0 1
4 6
1 1 2 2
1 2 4 2
Dữ liệu ra:
7
9

Giới hạn:

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