有一天，你遇到了一只大猩猩，它给了你一个包含 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$。你不知道该怎么处理这份礼物，所以你想拒绝它，但不幸的是，大猩猩坚持要你回答 $m$ 个询问。询问共有三种类型：

1. $l, r, k$ — 计算函数 $\text{gorilla}(l, r, k)$ 的值（定义见下文）；
2. $i, x$ — 执行赋值操作 $a_i := x$；
3. $l, r, c, b$ — 对于所有满足 $l \le i \le r$ 且不等式 $c \cdot a_i \le b$ 成立的下标 $i$，执行赋值操作 $a_i := c \cdot a_i$。

函数 $\text{gorilla}(l, r, k)$ 的定义如下：首先，将 $a_l, a_{l+1}, \dots, a_r$ 中所有拥有至多 $k$ 个不同质因数的数按原顺序写下。设得到的序列为 $y_1, y_2, \dots, y_s$（其中 $s$ 是得到的数的个数，$0 \le s \le r - l + 1$）。那么 $\text{gorilla}(l, r, k)$ 的值为这些数的交错和：$y_1 - y_2 + \dots + (-1)^{s+1} \cdot y_s$。若 $s = 0$，则该和被视为 $0$。

输入格式

第一行包含整数 $n$ 和 $m$ ($1 \le n, m \le 2 \cdot 10^5$)，分别表示数组元素的个数和询问的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)，表示数组的元素。

接下来的 $m$ 行描述了询问（所有参数均为整数）：

• “$1\ l\ r\ k$” ($1 \le l \le r \le n, 1 \le k \le 10^6$) — 第一类询问；
• “$2\ i\ x$” ($1 \le i \le n, 1 \le x \le 10^6$) — 第二类询问；
• “$3\ l\ r\ c\ b$” ($1 \le l \le r \le n, 1 \le c, b \le 10^6$) — 第三类询问。

输出格式

对于每个第一类询问，在单独的一行中输出答案。

样例

输入 1

10 5
5 14 62 36 9 1911 10 12 13 35
1 2 6 2
2 5 120
1 3 9 1
3 4 6 7 993
1 1 10 3

输出 1

-21
13
1736