Piggy is developing a fantastic calculator. This calculator innovatively invents a binary operator symbol that perfectly mixes addition and multiplication, which we call   ( is a positive integer).

The value of  is equal to . The precedence between operators is that the higher the , the higher the priority. The higher priority goes first. For example,has a higher priority than , so you must calculate  before . The operators are left-associative. Between the operators with the same priority, you should calculate them from left to right. For example, in the expression , you must calculate firstly.

Now, Piggy wants to ask you to help him implement a function. There is an expression with numbers and operators. At the same time, there are queries, each of them shaped as . You need to calculate the result of the sub-expression formed by the -th number to the -th number.

输入描述:

The first line contains one positive integer   -- the length of the expression.

The second line contains  positive integers   -- the  numbers from left to right in the expression.

The third line contains  positive integers  , where the -th operator from left to right is  and is  between the -th number and the -th number.

The forth line contains one positive integer   -- the number of queris.

The next  lines describe the queries, where the -th line contains two integers  .

输出描述:

For each query, print an integer in one line -- the result of the calculation. Since the answer may be very large, you only need to print the answer modulo .

5
1 2 3 4 5
5 2 3 4
2
1 5
2 4

264
46

In the first query, the equation is .

In the second query, the equation is .