Range GCD Queries
You are given an array of
n elements and q queries. There are two types of queries: compute the greatest common divisor (GCD) for the given range and update an element at a specified location. Your task is to process the queries efficiently.Input
The first line of the input contains two integers
n and q (1 ≤ n, q ≤ 100 000), representing the number of elements in the array and the number of queries, respectively.The second line contains n space-separated integers
The following
q lines each represent a query:- For range GCD queries: The line starts with the number 1 followed by two integers
and(), representing the range of indices[]for which the GCD needs to be calculated.
- For array update queries: The line starts with the number 2 followed by two integers
and(), representing the indexof the element to be updated and its new value.
Output
For each range GCD query, print the GCD value of the elements within the given range in a separate line.
Examples
Input | Output |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 4
2
2 |
Constraints
Time limit: 0.8 seconds
Memory limit: 512 MB
Output limit: 1 MB