Given a sequence $S$ of length $n$, where each element $S_i$ is an integer. It is guaranteed that any two distinct elements in the sequence are pairwise coprime. Now there are $T$ queries or modifications:

Query: Given an interval $[l, r]$, determine whether this interval is a perfect interval. An interval is defined to be perfect if, for every number $x$ appearing in the interval, letting its occurrence count be $c_x$, we have $c_x \mod x = 0$.

Modification: Change the number at position $p$ to $x$. After the modification, it is still guaranteed that any two distinct elements in the sequence are pairwise coprime.

Input

The first line contains two integers $n, T$ $(n, T \le 200000)$. Here $n$ denotes the length of the sequence, and $T$ denotes the total number of queries and modifications.

The second line contains $n$ integers, representing the sequence.

The next $T$ lines each contain an integer $tp$ indicating the operation type. If $tp = 0$, the operation is a query, followed by two integers $l, r$ indicating the query interval. If $tp = 1$, the operation is a modification, followed by two integers $p, x$ indicating that the number at position $p$ is changed to $x$ $(S_i, x \le 10^8)$.

Output

For each query, output a line yes or no indicating whether the queried interval is a perfect interval.

Examples

Input 1

8 5
2 2 3 3 3 1 5 1
0 1 5
0 1 3
0 6 8
0 6 6
0 1 8

Output 1

yes
no
no
yes
no

Input 2

6 9
2 2 3 3 3 1
0 1 6
1 3 2
0 1 6
1 4 2
0 1 4
1 5 2
0 1 6
1 6 2
0 1 6

Output 2

yes
no
yes
no
yes