Point Assign, Range GCD

Difficulty: 1700 5000 ms 128 MB

segment-tree

Support U i v (assign a_i = v) and Q l r (print the gcd of a_l..r).

Input: the first line has N and Q; the second line has the array; each of the next Q lines is an operation.

Output: one line per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ values ≤ 10⁶

Sample Tests

5 3
3 1 4 1 5
Q 1 5
U 2 9
Q 1 3

1
1

1 1
7
Q 1 1

7

Read the Editorial