P1033蝶恋花（flutter）

【题目背景】

远行归来时，花庭恰逢四月。Ehundategh 想起自己曾害怕风雪会使一切重归离散，于是将那场未曾发生在这条世界线中的错过写下：

《蝶恋花·破雪》

念却韶光醉人间，人间四月，四月香腮写。东花亭亭缀满树，树影幢幢蔽幽路。

不期异雪散风助，风助云起，云起绕花树。怎望白日堪雨落，落雨怨君伤行错。

ESC 读完以后牵住了他的手。异雪仍会落下，但这一次，两个人会共同记住每一次花开，也会共同让受损的花木再次盛放。

【题目描述】

花庭中有连续排列的 $n$ 片花圃，编号为 $1\sim n$。第 $i$ 片花圃当前的繁盛程度为整数 $a_i$，称为它的盛放值。

为了不让曾经的美好被之后的风雪抹去，二人还为每片花圃记录一个留芳值 $b_i$。最初 $b_i=a_i$。每次对花圃的维护结束后，都令 $b_i\leftarrow\max(b_i,a_i)$。因此，一片花圃的留芳值始终等于它从最初到当前曾经达到过的最大盛放值。

四月的天气并不总是温和。一阵暖风可能让一段花圃同时繁盛，突来的寒意也可能让它们一同衰落。枝叶生长得过盛时，Ehundategh 与 ESC 还会沿着连续的一段花圃修剪，将其中高于同一界限的盛放值压低到这个界限，而原本没有超过界限的花圃不会改变。

为了同时照看花圃此刻的模样与一路以来留下的最好光景，二人将之后的 $q$ 次记录依次编号。每次记录先给出一个整数 $p$，表示当天发生的事情。若这次记录改变了盛放值，应先完成整段花圃的改变，再立即更新每片花圃的留芳值，然后才会处理下一次记录。

五种记录的含义如下：

1. 当 $p=1$ 时，记录写作 1 l r k。区间 $[l,r]$ 内的每片花圃受到相同的天气影响，其盛放值增加 $k$。其中 $k$ 可以为负数。
2. 当 $p=2$ 时，记录写作 2 l r v。二人修剪区间 $[l,r]$ 内过盛的枝条，将每片花圃的盛放值改为它与 $v$ 中的较小值，即令 $a_i\leftarrow\min(a_i,v)$。
3. 当 $p=3$ 时，记录写作 3 l r。二人想知道区间 $[l,r]$ 内所有花圃的盛放值之和。
4. 当 $p=4$ 时，记录写作 4 l r。二人想知道区间 $[l,r]$ 内最大的盛放值。
5. 当 $p=5$ 时，记录写作 5 l r。二人想知道区间 $[l,r]$ 内最大的留芳值。

请你依次回答所有询问。

【输入格式】

从文件 $\textbf{\textit{flutter.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

第一行包含两个整数 $n,q$，分别表示花圃数量和记录次数。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每片花圃最初的盛放值。

接下来 $q$ 行，每行首先输入一个整数 $p$，表示记录的类型，随后按照题目描述输入对应的参数。

【输出格式】

输出到文件 $\textbf{\textit{flutter.out}}$ 中。

对于每次 $p\in\{3,4,5\}$ 的记录，输出一行一个整数，表示对应询问的答案。

【样例 1 输入】

10 125 631 2 3 4 543 2 551 1 3 364 2 472 3 4 185 1 593 1 4

【样例 1 输出】

1142636411

【说明/提示】

【样例 1 解释】

第一次询问时，区间 $[2,5]$ 内花圃的盛放值之和为 $2+3+4+5=14$。

第二次记录结束后，所有花圃的盛放值依次为 $4,5,6,4,5$。修剪结束后，它们的盛放值变为 $4,5,1,1,5$，但第三片与第四片花圃已经达到过的繁盛程度仍被记录在留芳值中，因此最大的留芳值为 $6$。

【样例 2】

见选手目录下的 $\textbf{\textit{flutter/flutter2.in}}$ 和 $\textbf{\textit{flutter/flutter2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{flutter/flutter3.in}}$ 和 $\textbf{\textit{flutter/flutter3.ans}}$。

该组样例符合测试点 $5\sim 9$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{flutter/flutter4.in}}$ 和 $\textbf{\textit{flutter/flutter4.ans}}$。

该组样例符合测试点 $10\sim 15$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{flutter/flutter5.in}}$ 和 $\textbf{\textit{flutter/flutter5.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10$，$1\leq n,q\leq 5\times 10^5$，$-5\times 10^8\leq a_i\leq 5\times 10^8$，$p\in\{1,2,3,4,5\}$，$1\leq l\leq r\leq n$，$-2\times 10^3\leq k\leq 2\times 10^3$，$-5\times 10^8\leq v\leq 5\times 10^8$。单个测试点内所有测试数据的 $n$ 之和不超过 $5\times 10^5$，$q$ 之和不超过 $5\times 10^5$。

特殊性质 A：保证不存在 $p=2$ 的记录。

特殊性质 B：保证不存在 $p=5$ 的记录。