Calculi is Lambda's older brother. Lambda is mischievous and always annoys Calculi by asking silly questions. This time around, Lambda would like to surprise Calculi by asking a challenging and interesting question. To that end, Lambda gives Calculi an array of integers, , followed by queries. Each query is of two types:
- : Find the minimum positive integer, , such that each element in subarray divides .
- : Multiply the value at by . That is , where is the updated value.
Your task is to help Calculi tackle this challenge. For each query of type , find the value of . As this value can be very large, print the modulo , i.e., . For query of type , update the required element.
Input Format
The first line contains an integer, , which represents the length of array, .
In second line, there are space-separated integers, , representing the elements of .
In third line, there is another integer, , which is the count of queries to follow.
Then follows lines, each representing a query of one of the types described above.
Constraints
- , where
Output Format
For each query of type Q l r, print the value of on a new line.
Sample Input
5
2 5 6 1 9
7
Q 0 4
U 1 2
Q 0 2
Q 3 4
Q 2 4
U 3 8
Q 2 3
Sample Output
90
30
9
18
24
Explanation
Query 1 (Q 0 4): Calculi has to find for (sub)array which is 90.
Query 2 (U 1 2): . Now updated array is .
Query 3 (Q 0 2): for subarray is .
Query 4 (Q 3 4): for subarray is .
Query 5 (Q 2 4): for subarray is .
Query 6 (U 3 8): Updated array is .
Query 7 (Q 2 3): for subarray is .
Tested by Wanbo