Shawn has a magical data structure.
Originally it takes an array of Integers (1-based index ) $A$ whose length is $n$ , and it supports these operations:
M p x
means update $A[p] = x$
D L R x
which enumerate every number index from L to R inclusive , divide each number by $x$ ( integer division , $3 / 2 = 1$ , $5 / 10 = 0$ )
Q L R
you need to output the sum for number from L to R inclusive. Basically $A[L] + A[L + 1] + ... + A[R]$
First line 1 number $n$.
Second line $n$ numbers $A_{i}$.
Third line 1 number $m$.
The rest of $m$ lines , each line contains an operation.
$1 \le n,m \le 10^{5}$
$1 \le A_{i},x \le 10^{9}$
$1 \le L , R , p \le n$
For each query , output a number indicates the answer.
5
1 2 3 4 5
4
Q 1 3
D 1 3 2
M 2 2
Q 1 36
3