Greatest common divisor of two integers a and b, denoted gcd(a, b), is the greatest integer c that divides both a and b.

It holds that gcd(a, b) = gcd(b, a) and gcd(a, 0) = a. We also define that gcd(x_1, x_2, \ldots, x_k) = gcd(x_1, gcd(x_2, x_3, \ldots, x_k)).

A simple and efficient way of computing gcd(a, b) is the Euclidean algorithm, which runs in logarithmic time:

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

You are given a list x with n numbers, and q queries.

There are two types of queries:

1. Replace the number in the list at index i with v.
2. Compute gcd(x_a, x_{a+1}, \dots, x_b).

Input

On the first line there are two integers n and q: the number of elements in the list and the number of queries.

On the second line there are n integers: x_1, x_2, \ldots, x_n: the initial values in the list.

q lines follow, describing the queries. Each line is either "u i v" or "q a b": a type 1 or 2 query, respectively. There is at least one type 2 query.

Output

For each type 2 query, output a single integer: gcd(x_a, x_{a+1}, \dots, x_b).

Constraints

• 1 \le n, q \le 10^5
• 0 \le x_i, v \le 10^9
• 1 \le a \le b \le n
• 1 \le i \le n

Examples

Input:

4 3
2 4 6 3
q 1 4
q 1 3
q 3 4

Output:

1
2
3

Input:

4 4
2 4 6 3
u 2 12
q 1 4
q 1 3
q 2 3

Output:

1
2
6