大样例

【题目描述】

黑鸭有一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$ ,他每次会进行以下三种操作之一：

1.给定三个正整数 $l,r,v$ ，把 $a_l \sim a_r$ 都加上 $v$。

2.给定三个正整数 $l, r, v$，把 $al ∼ ar$ 都变为 $v$。

3.给定两个整数 $l, r$，求子区间 $[a_l, a_l + 1,...,a_r]$ 的奇异度。

一个序列 $b_1, b_2, . . . , b_n$ 的奇异度定义为，每次任选一个位置 $b_i$ 并将其变为 $\lfloor \sqrt{b_i \rfloor}$，使得 $b_1 ∼ b_n$ 全相同所需的最小操作次数。

【输入格式】

从文件 $dseq.in$ 中读入数据。

第一行两个正整数 $n$, $q$。

第二行 $n$ 个正整数 $a_1, a_2, . . . , a_n$，表示序列 $a$。

接下来 $q$ 行，每行第一个整数 $op$ 表示操作种类。当 $op = 1$ 时，后跟三个整数 $l, r, v$，表示进行 第一种操作；当 $op = 2$ 时，后跟三个整数 $l, r, v$ 表示进行第二种操作；当 $op = 3$ 时，后跟三个整数 $l, r$ 表示查询 $a_l ∼ a_r$ 的奇异度。

【输出格式】

输出到文件 $dseq.out$ 中。

对于每个 $op = 3$ 的操作，输出一行整数表示此次查询的结果。

【样例 1 输入】

3 4
11 45 14
2 1 2 6
3 1 3
1 2 3 30
3 1 3

【样例 1 输出】

6
2

【样例 1 解释】

第一个询问时，序列为 ${6, 6, 14}$，最优策略为对每个元素进行两次操作，使得序列变为 ${1, 1, 1}$， 答案为 $6$。 第二个询问时，序列为 ${6, 36, 44}$，最优策略为对 $a_2, a_3$ 各自进行一次操作，使得序列变为 ${6, 6, 6}$，答案为 $2$。

【样例 2】

见下发文件目录下的 dseq/ex_dseq2.in 与 dseq/ex_dseq2.ans。

【样例 3】

见下发文件目录下的 dseq/ex_dseq3.in 与 dseq/ex_dseq3.ans。

【数据范围与提示】

对于 100% 的数据，有 $1 ≤ n, q ≤ 250000, 1 ≤ a_i ≤ 10^9 , 1 ≤ l ≤ r ≤ n$。对于 $1$ 操作，有$ 1 ≤ v ≤ 4000$，对于 $2$ 操作，有 $1 ≤ v ≤ 10^9$