Bedao Mini Contest 07 - ARCHITECT

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nhân ngày sinh nhật, Minh được bố mẹ thưởng cho một chiếc bánh sinh nhật có dạng hình hộp chữ nhật và có ~k~ tầng kem, mỗi tầng kem này được tạo bởi các ô kem nhỏ hơn có hình lập phương ~1 \times 1 \times 1~ xếp lại với nhau, như thế luôn đảm bảo rằng ở tầng kem bất kỳ sẽ luôn có chiều dài là ~n~, chiều rộng là ~m~ và chiều cao luôn là ~1~. Là một người rất sành ăn nên Minh biết độ ngon của từng ô kem lập phương này nên nếu coi một tầng kem là một bảng hình chữ nhật thì độ ngon của ô kem lập phương thuộc hàng ~i~, cột ~j~ và tầng kem thứ ~z~ có giá trị là ~a_{i,j,z}~ . Khổ nỗi bánh kem thì rất to, mà bạn đến dự sinh nhật thì ít nên để làm cho buổi sinh nhật thêm "mặn mà" hơn, thay vì rảc muối lên chiếc bánh sinh nhật thì Minh quyết định trổ tài cắt chiếc bánh của mình từ hình hộp chữ nhật thành hình kim tự tháp có chiều rộng mặt đáy là ~X~, chiều dài mặt đáy là ~Y~ và có độ cao là ~Z~, khi bắt đầu cắt bánh, Minh quyết định cắt ở ô kem trái trên của mặt đáy có tọa độ là ~(x,y,g)~. Do là người rất cẩn thận nên trước khi cắt bánh, Minh muốn khảo sát với nhiều câu hỏi để nếu cắt bánh từ hình hộp chữ nhật thành kim tự tháp có chiều rộng mặt đáy là ~X~, chiều dài mặt đáy là ~Y~ và độ cao là ~Z~ thì Minh sẽ được tổng giá trị độ ngon là bao nhiêu, biết rằng kim tự tháp mà Minh muốn cắt là kim tự tháp có nhiều tầng với tầng trên luôn nhỏ hơn tầng dưới được minh họa như sau:

hình

Input

  • Dòng đầu tiên là ~3~ số ~n~, ~m~, ~k~ lần lượt là chiều dài ~n~, chiều rộng ~m~ và có ~k~ tầng kem của chiếc bánh sinh nhật ~(1 \leq n \times m \times k \leq 5 \times 10^5)~
  • ~k~ khối dòng tiếp theo, khối dòng thứ ~t~ ~(1 \leq t \leq k)~ có ~n~ dòng, và ~m~ cột. Dòng thứ ~i~ ~(1 \leq i \leq n)~ thuộc khối dòng thứ ~t~ có ~m~ số nguyên là độ ngon của các ô kem có hình lập phương ~1 \times 1 \times 1~ và ô kem thứ ~j~ ~(1 \leq j \leq m)~ có giá trị độ ngon là ~a_{i,j,t}~ ~(1 \leq a_{i,j,t} \leq 10^6)~, với mỗi khối dòng như vậy được quy ước là một tầng kem của hình hộp chứ nhật
  • Dòng tiếp theo chứa số nguyên dương ~Q~ ~(1 \leq Q \leq 10^5)~ là số câu hỏi của Minh
  • ~Q~ dòng tiếp theo, mỗi dòng là ~6~ số nguyên dương ~X, Y, Z, x, y, g~ ~(1 \leq X, Y, Z \leq 10^6; 0 \leq x, y, g \leq 10^5)~

Output

  • In ra ~Q~ dòng mỗi dòng là độ ngon của kim tự tháp với ~X, Y, Z, x, y, g~ tương ứng, nếu không tính được thì in ra ~-1~

Sample Input

4 4 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 
4 4 2 1 1 1

Sample Output

20

Subtask

  • ~30\%~ số test có ~n \times m \times k \leq 100~
  • ~70\%~ số test còn lại không có điều kiện gì thêm

Note

Quy ước tầng thứ ~1~ là đáy của hình hộp chữ nhật cũng như là đáy của hình kim tự tháp

Tại tầng thứ ~1~, ta chọn cắt từ ô kem hình lập phương có tọa độ là ~(1,1,1)~ đến hết lớp kem của tầng ~1~ vì ta quyết định không cắt ô kem nào ở ngoài biên cả, ta được kết quả là ~ans_1 = 16~

Tại tầng thứ ~2~, ta chọn cắt từ ô kem hình lập phương có tọa độ là ~(2,2,2)~ đến hết lớp kem của tầng ~2~ thỏa mãn chỉ cắt bỏ ô biên bên ngoài vào ~1~ ô, tức tầng kem bị cắt bỏ ~12~ ô kem để được ~4~ ô kem còn lại, ta được kết quả là ~ans_2 = 4~

Vậy tổng cộng độ ngon của kim tự tháp sẽ là ~ans_1 + ans_2 = 20~

Quá trình cắt bánh được mô tả như sau:


Comments

Please read the guidelines before commenting.


There are no comments at the moment.