Let A = {a0, a1, a2, a3, ...., an−1} be an array. We define a recursive operation Op on array A as follows

Op(A) = Op(two(A)) + Op(one(A)) + Op(zero(A)) if n > 1
           = A otherwise

Here, zero(A) = {a0, a3, a6, ..} i.e. an array formed by elements whose indices are divisible by 3. Similarly, one(A) = {a1, a4, a7, a10, ...} and two(A) = {a2, a5, a8, a11..}. Also, + is the concatenation operation.

For example, if A = {0, 1, 2, 3, 4, 5}. Then Op(A) will be calculated as

Op(A) = Op({2, 5}) + Op({1, 4}) + Op({0, 3})
           = Op({}) + Op({5}) + Op({2}) + Op({}) + Op({4}) + Op({1}) + Op({}) + Op({3}) + Op({0})
           = {5, 2, 4, 1, 3, 0}

We define an query on an array B as taking the sum of all elements bk where i ≤ k ≤ j and l ≤ bk ≤ r.

Input

First line contains size n of array C. ( n ≤ 10^5 ) -

Second line contains n integers c0, c1, c2, ...cn−1. ( |ci | < 10^6 ) -

Third line contains q, number of queries. (q ≤ 10^5 ) -

Next q lines contains four integers i, j, l, r. (0 ≤ i < n, i ≤ j < n, l = −10^6 − 1, r = 10^6 + 1)

Note that l, r are fixed

Output

You have to output q integers corresponding to each query on a separate line.

Example

Input:
4
1 -1 5 4
1
0 3 -1000001 1000001

Output:
9