#P18276. Shiori

Shiori

Shiori

“普通”和“平常”究竟是什么意思?手里的这把尺子,似乎也量不清楚。

企鹅 Tomorin 收藏了许多石头。为了欣赏这些石头,她在地上摆了 nn 堆,第 ii 堆最初有 aia_i 颗石头,aia_i 是非负整数。她准备按以下指令移动石头,请你帮助处理这些操作。

  • 1 l r v:重新摆放第 ll 堆到第 rr 堆石头,使每堆恰好有 vv 颗。也就是对所有 l≤i≤rl\le i\le r,令 ai←va_i\leftarrow v。
  • 2 l r:Tomorin 不希望自然数出现遗漏。先计算区间当前石头数的 mex⁡\operatorname{mex},记为 ww;然后从她的收藏中给区间内每一堆都增加 ww 颗石头,即对所有 l≤i≤rl\le i\le r,令 ai←ai+wa_i\leftarrow a_i+w。
  • 3 l r:热心的饲养员 Rikki 想确认你有没有忽略 Tomorin,因此询问第 ll 堆到第 rr 堆石头的总数。输出 ∑i=lrai\sum_{i=l}^r a_i。

这里

$$\operatorname{mex}(S)=\min\bigl(\{0,1,2,3,\ldots\}\setminus S\bigr),$$

即没有出现在集合中的最小非负整数。例如 mex⁡({0,0,2})=1\operatorname{mex}(\{0,0,2\})=1,mex⁡({1,2})=0\operatorname{mex}(\{1,2\})=0。

类型 22 的操作只根据操作开始前的整个区间计算一次 ww,随后同时更新所有元素;大于等于 ww 的元素也必须增加 ww。

输入格式

第一行两个整数 n,mn,m(1≤n,m≤5×1051\le n,m\le5\times10^5),分别表示序列长度和操作数。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai≤5×1050\le a_i\le5\times10^5),表示初始序列。

接下来 mm 行,每行先给出一个整数 opi∈{1,2,3}op_i\in\{1,2,3\}:

  • 若 opi=1op_i=1,接下来三个整数 l,r,vl,r,v,满足 1≤l≤r≤n1\le l\le r\le n,0≤v≤5×1050\le v\le5\times10^5。
  • 否则,接下来两个整数 l,rl,r,满足 1≤l≤r≤n1\le l\le r\le n。

本题只有一个测试用例,输入开头没有测试用例数。初始值和类型 11 的赋值受上述上界限制,类型 22 操作后的值可以超过 5×1055\times10^5。

输出格式

对每个类型 33 的操作,输出一行一个整数,表示区间和。

类型 11 和类型 22 的操作不产生输出。答案可能超过 32 位整数范围,需要使用 64 位整数。

样例输入

5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5

样例输出

5
11
22