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.