- Prepare
- Functional Programming
- Persistent Structures
- Minimum Multiple
Minimum Multiple
Minimum Multiple
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