Implement an efficient data structure that allows you to modify array elements and calculate the GCD of several consecutive elements.
Input
The first line contains one natural number N (1 ≤ N ≤ 100000) — the number of numbers in the array.
The second line contains N numbers from 0 to 100000 — array elements.
The third line contains one natural number M (1 ≤ M ≤ 30000) — number of requests.
Each of the next M lines is a description of the request. First, a single letter is entered that encodes the type of request (s — compute GCD, u — update element value).
The s is followed by two numbers — numbers of the left and right borders of the segment.
The u is followed by two numbers — the element number and its new value.
Imprint
For each query s print the result. Print all numbers on one line separated by spaces.
| Input |
Output |
5
2 8 4 16 12
5
s15
s45
u 3 32
s25
s 3 3 |
2 4 4 32 |