B

你有一个长度为 $n$ 的序列 $a_1,a_2,\dots , a_n$ 。

你需要进行 $m$ 次操作。

1. 给定 $p,x$ ，将 $a_p$ 赋值为 $x$ 。
2. 给定 $l,r,k$ ，将所有 $l\leq i \leq r$ 的 $a_i$ 赋值为 $a_i\bmod k$ 。（$\bmod$ 为取模运算）
3. 给定 $l,r$ ，求所有 $l\leq i \leq r$ 的 $a_i$ 的最大值。

输入格式

第一行两个整数 $n,m$ 。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$ 。

接下来 $m$ 行每行第一个整数表示操作类型，后面 $2$ 或 $3$ 个整数表示这次操作给定的参数。

输出格式

对于所有操作 $3$ ，输出一行一个整数表示这次操作的答案。

输入样例

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

输出样例

3
2
5

数据范围

对于 $30\%$ 的数据，满足 $n,m\leq 2000$ 。

对于另外 $30\%$ 的数据，满足没有操作 $2$ 。

对于所有数据，满足 $n,m\leq 10^5,1\leq a_i,x,k\leq 10^9,1\leq l\leq r\leq n$ 。