Cyclic Sequence Operation Query

In this problem, you are given a sequence of n integers: a₁, a₂, ..., a_n. A single operation is defined as follows: for each index i (1-indexed), update a_i to a_i + a_{((i mod n) + 1)}. In other words, each element is increased by the element immediately following it, with the sequence considered cyclic (i.e. the element after a_n is a₁).

After performing the operation some number of times, you will be asked Q queries. Each query consists of two integers, x and y, which ask for the value at position y after x operations.

Observation: It can be derived that after x operations, the element at position y is given by:

\( a^{(x)}[y] = \sum_{j=0}^{x} \binom{x}{j} \cdot a[ ((y - 1 + j) \bmod n) + 1 ] \)

where \(\binom{x}{j}\) is the binomial coefficient. Note that the indices are taken in a cyclic manner.

Your task is to answer all queries efficiently.

inputFormat

The input begins with a line containing a single integer n (the number of elements in the sequence).

The next line contains n space-separated integers representing the sequence.

The following line contains a single integer Q representing the number of queries.

Each of the next Q lines contains two integers x and y. Each query asks you to compute the value at position y after x operations.

outputFormat

For each query, output a single integer — the value at position y after x operations. Answers for different queries should appear on separate lines.

sample

3
1 2 3
3
0 1
1 2
2 3

1
5
7