Problem Description

For a given positive integer \( N \) and integer triples \( (x, y, z) \) satisfying \( 1 \leq x, y, z \leq N \), an integer \( A_{x,y,z} \) is provided.

You are given \( Q \) queries in the following format. Answer each query accordingly.

For the \( i \)-th \( (1 \leq i \leq Q) \) query, an integer tuple \( (Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i) \) satisfying \( 1 \leq Lx_i \leq Rx_i \leq N \), \( 1 \leq Ly_i \leq Ry_i \leq N \), and \( 1 \leq Lz_i \leq Rz_i \leq N \) is given. Compute the following:

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

Input Format

The input is given from the standard input in the following format:

\( 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 \)

Output Format

Output \( Q \) lines. The \( i \)-th line should contain the answer for the \( i \)-th query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

10
26

Sample Input #2

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

Sample Output #2

687
3917
551
1631
5180
3311
1010
4326

Notes/Hints

Constraints

• \( 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) \)
• All inputs are integers.

Sample Explanation 1

For the first query, the value to be computed is \( A_{1,2,1} + A_{2,2,1} = 3 + 7 = 10 \). Therefore, output \( 10 \). For the second query, the value to be computed is \( A_{2,1,1} + A_{2,1,2} + A_{2,2,1} + A_{2,2,2} = 5 + 6 + 7 + 8 = 26 \). Therefore, output \( 26 \).

见题面 Input 部分

见题面 Output 部分