Bedao Regular Contest 06 - REWARDS

View as PDF

Submit solution


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

Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đô thị học viện là một nơi có công nghệ phát triển bậc nhất hành tinh B. Nơi đây nổi tiếng với việc đào tạo ra những siêu năng lực gia có sức mạnh to lớn. Misaka Mikoto là một trong những siêu năng lực gia mạnh nhất của thành phố. Gekota là một linh thú linh vật mà cô rất thích. Cô thích mọi thứ về Gekota, hôm nay lại có một cuộc thi về trí nhớ mà phần thưởng là một chiếc điện thoại có hình dáng của Gekota.

BTC cuộc thi sẽ đưa ra một hình hộp chữ nhật được ghép từ các khối vuông có kích thước ~1 \times 1 \times 1~ và bên trong mỗi khối vuông sẽ chứa một con số có ~X~ ~(|X| \leq 10^9)~. Vị trí của các khối vuông được biểu diễn bởi ~3~ số nguyên dương ~(x,y,z)~ ứng với tọa độ thuộc hệ trục tọa độ ~Oxyz~.

Người chơi sẽ phải dùng siêu năng lực của mình để nhìn thấu hết các số trong từng ô vuông và tọa độ tương ứng của nó. Theo như thể thức chương trình hàng năm, BTC sẽ đưa ra các câu hỏi có dạng ~(x_1, y_1, z_1; x_2, y_2, z_2)~ yêu cầu người chơi tính tổng các số có tọa độ ~(x, y, z)~ thỏa mãn ~(x_1 \leq x \leq x_2, y_1 \leq y \leq y_2, z_1 \leq z \leq z_2)~ và người trả lời nhanh nhất sẽ nhận được ~1~ điểm. Người nào trả lời đúng càng nhiều thì phần thưởng sẽ càng lớn.

Nhưng để thử thách người chơi năm nay, BTC đã chuẩn bị một hình hộp chữ nhật có kích thước ~m \times n \times p~ gồm các ô vuông ~1 \times 1 \times 1~ có thể thay đổi giá trị theo thời gian. Tức là trong thời gian chuẩn bị của thí sinh sẽ có ~T~ thời điểm, mỗi thời điểm các ô vuông sẽ có giá trị khác nhau. Ô vuông có tọa độ ~(x, y, z)~ vào thời điểm ~t~ sẽ có giá trị là ~a_{x,y,z,t}~ và mỗi câu hỏi lần này lại có dạng ~(x_1, y_1, z_1, t_1; x_2,y_2,z_2,t_2)~ tức là yêu cầu tính tổng các giá trị ~a_{x,y,z,t}~ thỏa mãn ~(x_1 \leq x \leq x_2, y_1 \leq y \leq y_2, z_1 \leq z \leq z_2, t_1 \leq t \leq t_2)~. Tuy thể thức câu hỏi thay đổi nhưng thể thức tính điểm vẫn giữ nguyên: có tổng cộng ~T~ câu hỏi, mỗi câu trả lời đúng và nhanh nhất sẽ nhận được ~1~ điểm và khi đạt được một mức điểm nhất định thì sẽ nhận được phần thưởng ở mốc đó. Đương nhiên để nhận được phần thưởng đặc biệt thì phải đạt được ~T~ điểm, tức là cô phải trả lời đúng và nhanh nhất hết toàn bộ ~T~ câu hỏi. Bạn hãy giúp Misaka Mikoto nhé.

Input

  • Dòng đầu tiên chứa ~4~ số nguyên dương ~n~, ~m~, ~p~, ~q~ ~(m, n, p, q \leq 40)~.
  • Dòng thứ hai gồm ~n \times m \times p \times q~ các giá trị ~a_{1,1,1,1} , a_{1,1,1,2} ,\dots, a_{1,1,1,q}, a_{1,1,2,1}, \dots, a_{1,1,2,q}, \dots, a_{1,1,p,q}, \dots, a_{1,n,p,q}, \dots,a_{m,n,p,q}~ ~(a_{x,y,z,t} \leq 10^9)~.
  • Dòng tiếp theo là một số nguyên dương ~T~ cho biết số câu hỏi mà chương trình đặt ra ~(1 \leq T \leq 10000)~.
  • ~T~ dòng tiếp theo là các câu hỏi có dạng ~(x_1, y_1, z_1, t_1; x_2,y_2,z_2,t_2)~ với ~(x_1 \leq x_2 \leq n, y_1 \leq y_2 \leq m, z_1 \leq z_2 \leq p, t_1 \leq t_2 \leq q)~.

Output

  • Gồm ~T~ dòng, mỗi dòng là tổng của các giá trị ~a_{x,y,z,t}~ thỏa mãn ~(x_1 \leq x_i \leq x_2, y_1 \leq y_i \leq y_2, z_1 \leq z_i \leq z_2, t_1 \leq t_i \leq t_2)~

Sample Input

2 2 2 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3
1 1 1 1 2 2 2 2
2 2 1 1 2 2 2 2
1 1 2 2 2 2 2 2

Sample Output

136
58
40

Subtask

  • ~30\%~ số test là ~n,m,p,q \leq 10~
  • Số test còn lại không giới hạn gì thêm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.