题目描述

输入一个正方体 $A$。该正方体的长宽高都为 $N$。该正方体的位置由 $i,j,k$ 确定，每个位置的数字是 $A_{i,j,k}$。现在有 $Q$ 组查询，每次查询要求出一个子立方体内所有位置的数字之和。

形式化题意如下：

给你一个正整数 $N$ 和一个整数 $A_{x,y,z}$ ，每个整数 $(x, y, z)$ 的三元组都是 $1 \leq x, y, z \leq N$ 。

你将得到以下格式的 $Q$ 个查询，必须按顺序处理。

对于第 $i$ 个查询 $(1 \leq i \leq Q)$ ，您将得到一个整数元组 $(x_1, x_2, y_1, y_2, z_1, z_2)$ ，其中有 $1 \leq x_1 \leq x_2 \leq N$ 、 $1 \leq y_1 \leq y_2 \leq N$ 和 $1 \leq z_1 \leq z_2 \leq N$ 。求

$\displaystyle{\sum_{x=x_1}^{x_2} \sum_{y=y_1}^{y_2} \sum_{z=z_1}^{z_2} A_{x,y,z}}$

输入格式

第一行输入一个整数 $n$

接下来一共输入 $n$ 个 $n\times n$ 的矩阵。你可以把一个边长为 $n$ 的正方体理解为 $n$ 层的二维矩阵，每一层都是一个 $n\times n$ 的二维矩阵。

然后输入一个数字 $q$ 代表 $q$ 组查询。

每一组查询输入 $6$ 个整数空格隔开 $x_1,x_2,y_1,y_2,z_1,z_2$

输出格式

输出一共输出 $q$ 行，每行一个整数代表答案。

2
1 2
3 4
5 6
7 8
2
1 2 2 2 1 1
2 2 1 2 1 2

10
26

样例 1 解释

对于第一个查询，所求的值是 $A_{1,2,1} + A_{2,2,1} = 3 + 7 = 10$ 。因此，打印 $10$ 。

对于第二个查询，所求的值是 $A_{2,1,1} + A_{2,1,2} + A_{2,2,1} + A_{2,2,2} = 5 + 6 + 7 + 8 = 26$ 。因此，打印 $26$ 。

3
733 857 714
956 208 257
123 719 648
840 881 245
245 112 746
306 942 694
58 870 849
13 208 789
687 906 783
8
3 3 3 3 1 1
1 3 2 3 3 3
2 2 2 3 1 1
1 3 1 1 1 1
2 3 2 3 2 3
1 2 1 1 1 2
3 3 2 2 1 3
1 2 2 3 2 3

687
3917
551
1631
5180
3311
1010
4326

样例 3

点我下载大样例

提示

对于 $50\%$ 的数据满足

• $1 \leq N \leq 100$
• $1 \leq Q \leq 10^{2}$
• $0 \leq A_{x,y,z} \leq 999$ $(1 \leq x, y, z \leq N)$

对于 $100\%$ 的数据满足

• $1 \leq N \leq 100$
• $1 \leq Q \leq 2 \times 10^{5}$
• $0 \leq A_{x,y,z} \leq 999$ $(1 \leq x, y, z \leq N)$