长方体区域求和

题目描述

给定一个正整数 $N$，并且对于每个满足 $1 \leq x, y, z \leq N$ 的整数三元组 $(x, y, z)$，给定整数 $A_{x,y,z}$。

接下来会按顺序处理 $Q$ 个如下格式的查询。

对于第 $i$ 个查询（$1 \leq i \leq Q$），给定一个整数六元组 $(Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i)$，满足 $1 \leq Lx_i \leq Rx_i \leq N$、$1 \leq Ly_i \leq Ry_i \leq N$、$1 \leq Lz_i \leq Rz_i \leq N$。求：

$\displaystyle{\sum_{x=Lx_i}^{Rx_i} \sum_{y=Ly_i}^{Ry_i} \sum_{z=Lz_i}^{Rz_i} A_{x,y,z}}$

输入格式

输入按以下格式从标准输入给出：

$N$
$A_{1,1,1}$ $A_{1,1,2}$ $\ldots$ $A_{1,1,N}$
$A_{1,2,1}$ $A_{1,2,2}$ $\ldots$ $A_{1,2,N}$
$\vdots$
$A_{1,N,1}$ $A_{1,N,2}$ $\ldots$ $A_{1,N,N}$
$A_{2,1,1}$ $A_{2,1,2}$ $\ldots$ $A_{2,1,N}$
$A_{2,2,1}$ $A_{2,2,2}$ $\ldots$ $A_{2,2,N}$
$\vdots$
$A_{2,N,1}$ $A_{2,N,2}$ $\ldots$ $A_{2,N,N}$
$\vdots$
$A_{N,1,1}$ $A_{N,1,2}$ $\ldots$ $A_{N,1,N}$
$A_{N,2,1}$ $A_{N,2,2}$ $\ldots$ $A_{N,2,N}$
$\vdots$
$A_{N,N,1}$ $A_{N,N,2}$ $\ldots$ $A_{N,N,N}$
$Q$
$Lx_1$ $Rx_1$ $Ly_1$ $Ry_1$ $Lz_1$ $Rz_1$
$Lx_2$ $Rx_2$ $Ly_2$ $Ry_2$ $Lz_2$ $Rz_2$
$\vdots$
$Lx_Q$ $Rx_Q$ $Ly_Q$ $Ry_Q$ $Lz_Q$ $Rz_Q$

输出格式

输出 $Q$ 行。 第 $i$ 行输出第 $i$ 个查询的答案。

样例

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$。

对于第 2 个查询，所求的值为 $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

数据范围

• $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$）
• $1 \leq Lx_i \leq Rx_i \leq N$（$1 \leq i \leq Q$）
• $1 \leq Ly_i \leq Ry_i \leq N$（$1 \leq i \leq Q$）
• $1 \leq Lz_i \leq Rz_i \leq N$（$1 \leq i \leq Q$）
• 所有输入值均为整数。