Problem10957--【模板题】 三维区间和

10957: 【模板题】 三维区间和

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

在公元 3xxxx 年,三体人开始进攻地球。
三体人的太空派出 $n\times m \times l$ 艘战舰,在太空中拍成一个 $n$ 层 $m$ 行 $l$ 列的立方体。其中,第 $i$ 层第 $j$ 行第 $k$ 列的战舰记为战舰 $(i,j,k)$,对应的生命值为 $a(i,j,k)$。
为了应对危机,地球需要进行 $q$ 轮估计,妹婿需要计算出阵型中指定立方体区域中战舰的生命值总和。
你能帮忙计算吗?

Input

第一行包括三个整数 $n,m,l\ (1 \leq n,m,l \leq 200)$。
其后 $n$ 组,每组包括 $m$ 行,每行有 $l$ 个数组。每组之间用一个空行隔开。对于每个数 $0 < a(i,j,k) \leq 10^5$。
接下来一行包括一个整数 $q\ (1 \leq q \leq 10^5)$,表示询问的次数。
接下来包括 $q$ 行,每行都有 $6$ 个数,依次是 $x_1,y_1,z_1,x_2,y_2,z_2\ (1 \leq x_1 \leq x_2 \leq n,\ 1 \leq y_1 \leq y_2 \leq m,\ 1 \leq z_1\leq z_2 \leq l)$,表示一个立方体的两个对角顶点 $(x_1,y_1,z_1),\ (x_2,y_2,z_2)$。这两个顶点可以确定一个立方体。

Output

对于 $q$ 次询问,每一轮询问,输出立方体区域内战舰的生命总和。由于总和可能会比较大,需要对所有结果模 $10^9+7$。

Sample 1 Input

1 2 3
1 2 3
4 5 6

2
1 1 1 1 2 2
1 2 1 1 2 3

Sample 1 Output

12
15

Sample 2 Input

2 2 3
1 2 3
4 5 6

7 8 9
10 11 12

4
1 1 1 1 2 2
1 2 1 1 2 3
1 1 1 2 2 2
1 1 1 2 2 3

Sample 2 Output

12
15
48
78

Source/Category