背景

XYH有许多硬币
XYH喜欢玩硬币
XYH把硬币摞成多摞
XYH把硬币排成一排
XYH不时添加硬币
XYH有时想知道一些摞的硬币总数

描述

给出N及N个整数
M个操作o,l,r
o==0 表示询问[l,r]区间内数的和
o!=0 表示将[l,r]区间内小于o的数改为o

输入

第一行两个正整数N,M
第二行N个整数\(A_1\),\(A_2\),\(A_3\),...,\(A_N\)
接下来M行
每行三个整数o,l,r

输出

对于每个询问，输出一行一个整数，为区间和

样例

输入

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

输出

17
14
30
23

范围

50% N,M<=5000
70% N,M<=10000
90% N,M<=\(10^5\)
100% N<=\(2\ast 10^5\) M<=\(3\ast 10^6\) |\(A_i\)|<=\(10^4\) 0<=o<=\(M\ast 10^3\) 1<=l<=r<=N

限制

2s
256M