K-dimensional partial sum

Given a k-dimensional array of numbers a_i_1,i_2,...,i_k, where 1 ≤ i_j ≤ n_j for each j from 1 to k. For the specified ranges l_1, ..., l_k and r_1, ..., r_k, determine the following:

Input

The first line contains the integer k (1 ≤ k ≤ 6).

The second line provides the dimensions of the array - n_j (1 ≤ Πn_j ≤ 10^6). Following this, n_k rows of numbers are given, each not exceeding 1000, representing the array.

The next line contains the integer q (1 ≤ q ≤ 10^6), which is the number of queries. Each of the next q lines describes a query:

l_1, ..., l_k, r_1, ..., r_k (1 ≤ l_j ≤ r_j ≤ n_j).

Output

Output q numbers, each on a separate line, representing the answers to the queries.

Examples