Description

给定一个长度为$n$的数组a,$[a_1,a_2,...,a_n]$，并给定m次操作

m次操作由以下两种组成，查询与修改

1. 修改：修改第$pos$位为$val$
2. 查询：找到距离第$pos$位的元素$a_{pos}$的位置最近的互素的元素的距离并输出

互素代表$gcd(x,y) = 1$, $gcd$为最大公约数。

Format

Input

第一行两个整数，分别为$n,m$,分别代表a数组中有$n$个元素，$m$个操作

第二行有$n$个整数，第i个数为$a_i$

第$3$ - $3 + m$行每行代表一个操作，每行可能有两种情况,如果op为1操作为修改，后面跟上两个整数分别为pos,val，如果op为2则代表查询，后面跟上一个整数pos，代表你需要查找第pos位的元素$a_{pos}$的位置最近的互素的元素。

• op pos val
• op pos

Output

对于每一个操作2，输出对应的距离最近的互素的元素的距离。

Samples

5 2
1 2 3 4 5
1 2 1
2 3

1

Limitation

1s, 1024KiB for each test case.

for all case, $1 \le n,m \le 10^6$

所有数据均为随机生成