PyPy3でACが得られることは保証していますが、C++などのコンパイラ言語の使用を推奨します。

ストーリー

Awashくんは、ABC432Eで誤読をしました。 幸い、数分で誤読に気づき、ACすることができました。

しかし、数ヶ月後に、誤読した内容の問題を解かなければいけない状況に出くわしたようです…

問題文

kazuppaくん、Awashくん、ゆ～さん、ルクくんはクリスマスパーティーの準備をしています。Awashくんの担当は木を用意することです。

$N$ 本のOakの木が一列に並んでいる並木があります。左から $i$ 番目の木を、木 $i$ と表します。木 $i$ の高さは $A_i$ です。

Awashくんは、この並木からある連続する区間の木々を選び、接ぎ木や枝打ちである程度高さを揃えた上で、飾り付けをしようと思っています。 飾り付けに必要なオーナメントの個数を求めるため、飾りつける木の高さの合計が知りたいです。

Awashくんは、まだどの区間の木を飾り付けるか、またどのように木の高さを揃えるかを決めていないため、必要なオーナメントの個数を高速に求められるシミュレーションプログラムが欲しいです。

$Q$ 個のクエリが与えられるので、順に処理してください。各クエリは以下のいずれかの形式です。

• 1 x y: 木 $x$ を伐採し、高さが $y$ の木を新たに同じ場所に植える。すなわち、$A_x$ の値を $y$ に変更する。
• 2 l r a b: $l \leq i \leq r$ を満たす $i$ について、木 $i$ の高さを $a$ 以上 $b$ 以下に揃えたときの、木の高さの合計を求める。 すなわち、$\displaystyle \sum_{l \leq i \leq r} \max(a, \min(b, A_i))$ の値を求める。 $a$ 以上 $b$ 以下に揃えられた木は、次回以降のクエリに反映されない。

入力

$N\ Q$
$A_1\ A_2\ \dots\ A_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

ここで、$\mathrm{query}_q (1 \leq q \leq Q)$ は $q$ 番目のクエリを表し、以下のいずれかの形式で与えられます。

$1\ x\ y$

$2\ l\ r\ a\ b$

制約

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $0 \leq A_i \leq 10^5$
• $1$ 種類目のクエリについて
  • $1 \leq x \leq N$
  • $0 \leq y \leq 10^5$
• $2$ 種類目のクエリについて
  • $1 \leq l \leq r \leq N$
  • $0 \leq a \leq b \leq 10^5$
• 入力は全て整数

出力

$2$ 種類目のクエリの個数を $K$ として、$K$ 行出力してください。 $q (1 \leq q \leq K)$ 行目には、$2$ 種類目のクエリのうち $q$ 個目のものに対する答えを出力してください。

サンプル

6 5
1 4 6 3 2 5
2 2 5 3 5
1 2 7
1 4 0
2 4 5 4 9
2 2 3 2 5

15
8
10

10 10
77 76 29 58 47 46 97 35 75 96
1 7 63
2 7 9 31 67
1 7 87
2 1 10 52 78
2 1 5 2 44
2 3 5 78 84
2 3 8 2 58
2 4 8 44 77
1 6 71
2 4 4 34 70

165
650
205
234
273
272
58