Description
Vainglory bu...... Anyway you are given two integers 
and 
. Let's define 
.
Also you are given a sequence 
and an expression which contains only 
functions and some elements of 
like 
or 
(supposing 
).
Now you need to execute 
operations. In the 
-th operation, you are given two integers 
and 
. First you have to change 
into 
. Then output the result of the expression.
For convenience, you only need to output the remainder of the result divided by (i.e. the result 
) in each operation.
Recall the remainder 
of 
divided by is a non-negative integer such that 
for some integer 
and 
.
Sample #2 Explanation
In Sample #2: 
and 
. Sequence 
is 
. The expression is 
.
In the 1st operation: 
and 
. So after changing 
into 
, sequence becomes (still the same). So the expression 
. The remainder of 181 divided by 
is equal to 1.
In the 2nd operation: 
and 
. So after changing 
into 
, sequence becomes 
. So the expression . The remainder of 181 divided by is equal to 1.
In the 3rd operation: 
and 
. So after changing 
into 
, sequence becomes 
. So the expression 
. The remainder of 229 divided by is equal to 9.
Hint 1
In mathematics, there are two properties about modulo operation(suppose 
are integers and 
):
That is if you want to modulo the result of some expression which consists of only addition or/and multiplication, you could just modulo any part in the expression as long as remembering to modulo the final result.
Hint 2
In mathematics, 
is equal to 
rather than 
.
But if you execute printf("%d\n", -4 % 3) in C, you will get -1 rather than 2.
That's because C only guarantees (a / b) * b + a % b is equal to a (i.e. 
). That is a % b is equal to a - (a / b) * b. That's why you will get -1 rather than 2 in above case. Try yourself to fix this issue, if necessary.
Input
The first line contains two integers and (
).
The second line contains a integer 
(
) – the number of elements in the sequence .
The third line contains integers 
(
) – all the elements in the sequence .
The fourth line contains a string 
(
) – the expression you are given. The expression must consists of only function (at least one function) and integers which are the indexes corresponding to the elements of (
all the integers 
). Every character in the string must be f or ( or ) or , or digits and the expression must be legal.
The fifth line contains a integer 
(
) – the number of times you need to execute operations.
Then lines follow. Each line contains two integers 
and 
(
) – the content of each operation.
It's guaranteed that:
- The 1st testcase must be identical to the Sample #1 below
- For the first 5 testcases:
- For the first 7 testcases:
Output
For each operation, output the remainder of the result divided by then print a newline('\n') character.
Note: there are two sample below. "# Sample Input 1/2" and "# Sample Output 1/2" are not the part of input and output.
They are just for marking that the following content corresponds to which sample.