题目描述

小 $\gamma$ 有一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，有 $q$ 次操作：

1. 给定一个区间 $[l, r]$ 和一个整数 $v$，将 $a_i (i \in [l, r] \cap \mathbb N)$ 加上 $v$。

2. 给定一个位置 $p$ 与一个编号 $k$，查询 $a_p$ 在第 $k$ 次操作前到现在的所有历史版本中的数的最大公约数。

定义 $x$ 是 $y$ 的约数当且仅当存在整数 $z$ 满足 $x z = y$，两个数 $x$ 和 $y$ 的最大公约数为 $x$ 与 $y$ 各自约数的交集中最大的一个

输入格式

第 $1$ 行 $2$ 个整数 $\mathtt{n\ q}$。

第 $2$ 行 $n$ 个整数 $\mathtt{a_{0,1}\ a_{0,2}\ \dots\ a_{0,n}}$，表示 $\{a_i\}$ 的初值。

第 $3$ 行至第 $q + 2$ 行，每行为 $\mathtt{1\ l\ r\ v}$ 或 $\mathtt{2\ p\ k}$。

输出格式

若干行，每行 $1$ 个整数，表示每次 $2$ 操作的答案。

样例一

input

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

output

2
3
9

样例二

input

1 1
-1
2 1 1

output

1

限制与约定

本题采用子任务形式。

对于 $30\%$ 的数据，满足 $1 \leqslant n, q \leqslant 1000$。

对于 $50\%$ 的数据，满足 $1 \leqslant n, q \leqslant 40000$。

对于另外 $10\%$ 的数据，满足 $l_i = r_i$。

对于另外 $10\%$ 的数据，满足 $k_i = i$。

对于含以上共 $80\%$ 的数据，满足 $1 \leqslant n, q \leqslant 10^5$。

对于 $100\%$ 的数据，满足 $1 \leqslant n, q \leqslant 2.5 \times 10^5, 1 \leqslant l_i \leqslant r_i \leqslant n, |v_i|,|a_{0,i}| \leqslant 10^9, 1 \leqslant p_i \leqslant n, 1 \leqslant k_i \leqslant i$。注意不保证 $a_i$ 在任意时刻绝对值不超过 $10^9$。