K-dimensional partial sum

Input

The first line contains the integer $k$ ( $1 \leq k \leq 6$ 1 \leq k \leq 6).

The second line contains the dimensions of the array: $n_{j}$ n_j ( $1 \leq \prod n_{j} \leq 1 0^{6}$ 1 \leq \prod n_j \leq 10^6).

Then, the array numbers are given in $n_{k}$ n_k rows, each not exceeding $1000$ , describing the array.

The next line contains the integer $q$ ( $1 \leq q \leq 1 0^{6}$ 1 \leq q \leq 10^6) — the number of queries.

Each of the following $q$ lines contains a query: $l_{1}, \dots, l_{k}, r_{1}, \dots, r_{k}$ l_1, \ldots, l_k, r_1, \ldots, r_k ( $1 \leq l_{j} \leq r_{j} \leq n_{j}$ 1 \leq l_j \leq r_j \leq n_j).

Output

Print the answer for each query on a separate line.

Examples

Example 1

Loading