问题描述

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

给你 $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}}$。

数据规模

$1\leq N\leq 100$

$1\leq Q\leq 2×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)$

所有输入值都是整数。

输入

输入来自标准输入，格式如下:

$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

对于第一个查询，查找的值是 $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$。

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