Algorithms and Data Structures

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 (), representing the initial elements of the array.
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 index of 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.08 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue