Migrated from Lutece 2945 肯德吉全家桶

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 吉司机线段树 吉老师最近新开了一家肯德吉快餐店，你受宣传吸引前去点了一份肯德吉全家桶。结账时，你不幸发现没有足够的金钱来支付账单。吉老师看出了你的窘境，为了不为难你，他决定给你出一道题，如果能正确地回答他的每个问题，你就能免费享用本次肯德吉全家桶。

刚开始，吉老师给了你一个长度为 $n$ 的数列 $a$，然后他会进行共 $m$ 次对数列的修改操作和询问操作。每次询问你都需要给出相应的答案。

吉老师每次会给定一个区间 $[l, r]$，并对数列进行以下两种修改操作和四种询问操作：

• 操作 $1$：对于所有的 $i \in [l, r]$，将 $a_i$ 变为 $a_i + k$；
• 操作 $2$：对于所有的 $i \in [l, r]$，将 $a[i]$ 变为 $min (a[i], x)$；
• 操作 $3$：询问 $\underset{i = l}{\overset {r} {\sum {}}}{a_i}$ 的结果；
• 操作 $4$：令 $f (i)$ 表示修改操作中 $a_i$ 值的变化次数，询问 $\underset{i = l}{\overset {r} {\sum {}}}{f (i)}$ 的结果；
• 操作 $5$：令集合 $S_i$ 表示在修改操作中 $a_i$ 曾表示过的所有的数，$g(i)$ 表示集合 $S_i$ 中的最大的数，询问 $max \{g_{l}, g_{l + 1}...g_{r}\}$ 的结果；
• 操作 $6$：令集合 $S_i$ 表示在修改操作中 $a_i$ 曾表示过的所有的数，$h(i)$ 表示集合 $S_i$ 中的最小的数，询问 $min \{h_{l}, h_{l + 1}...h_{r}\}$ 的结果；

正当你苦恼之时，突然你想起了打车时一位司机师傅教给你的数据结构，于是轻松地解决了吉老师的问题。

Input

第一行输入两个整数 $n$ 和 $m$，分别表示数列 $a$ 的长度和操作次数。

接下来的一行一共输入 $n$ 个整数 $a_1, a_2 ... a_n$。

最后 $m$ 行，每行第一个整数 $opt$ 表示操作类型：

$opt = 1$，之后有三个数 $l$, $r$, $k$，表示操作 $1$；

$opt = 2$，之后有三个数 $l$, $r$, $x$，表示操作 $2$；

$opt = 3$, $4$, $5$, $6$，之后有两个数 $l$, $r$，分别表示操作 $3$, $4$, $5$, $6$。

Output

对于每一个询问操作，输入一行表示答案。

Samples

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

9
8
3
7

Constraints

$1 \leq n, m \leq 2 \times 10^5$，$1 \leq a_i, x \leq n$， $1 \leq l \leq r \leq n$， $-n \leq k \leq n$，$k \neq 0$

Resources

2023 UESTC ICPC Training for Data Structures