Tổng khối con

Cho khối lập phương dữ liệu $A$ kích thước $X\times Y\times Z$ gồm các số nguyên. Các chỉ số được đánh từ $1$ đến $X$ theo trục thứ nhất, từ $1$ đến $Y$ theo trục thứ hai, và từ $1$ đến $Z$ theo trục thứ ba.

Bạn cần trả lời $q$ truy vấn. Mỗi truy vấn cho sáu số nguyên $x_1,y_1,z_1,x_2,y_2,z_2$ với $x_1\le x_2$, $y_1\le y_2$, $z_1\le z_2$. Hãy tính tổng các phần tử $A[i][j][k]$ với $x_1\le i\le x_2$, $y_1\le j\le y_2$, $z_1\le k\le z_2$.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $X$, $Y$, $Z$, $q$.
• Tiếp theo là $X$ khối, mỗi khối gồm $Y$ dòng, mỗi dòng có $Z$ số nguyên mô tả $A[i][j][1],A[i][j][2],\dots ,A[i][j][Z]$. Các khối có thể được phân tách bởi dòng trắng tùy ý (không bắt buộc).
• $q$ dòng cuối, mỗi dòng chứa sáu số nguyên $x_1,y_1,z_1,x_2,y_2,z_2$ mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Ràng buộc

• $1\le X,Y,Z$ và $X·Y·Z\le {10}^6$
• $1\le q\le 2·{10}^5$
• $-{10}^9\le A[i][j][k]\le {10}^9$
• $1\le x_1\le x_2\le X$, $1\le y_1\le y_2\le Y$, $1\le z_1\le z_2\le Z$

Ví dụ

Ghi chú

Kết quả có thể vượt phạm vi số nguyên 32-bit, hãy dùng kiểu 64-bit.