#P18525. Stacks

Stacks

Stacks

有 nn 个初始为空的栈,编号为 1,2,…,n1,2,\ldots,n。按输入顺序执行 mm 个操作,操作有以下三种:

  • 1 l r x y:向编号在闭区间 [l,r][l,r] 内的每一个栈中,压入 xx 个值为 yy 的元素。
  • 2 l r w:对编号在闭区间 [l,r][l,r] 内的每一个栈,执行 ww 次出栈操作。一次出栈操作指:如果栈为空,什么也不做;否则弹出栈顶元素。
  • 3 k p q:查询编号为 kk 的栈中,从栈底开始数第 pp 个至第 qq 个元素的和。不存在的元素视为 0。

请处理所有操作。

输入格式

第一行包含两个整数 n,mn,m(1≤n,m≤1051\le n,m\le10^5)。

接下来 mm 行,每行按时间顺序描述一个操作:

  • 1 l r x y:1≤l≤r≤n1\le l\le r\le n,1≤x,y≤1051\le x,y\le10^5。
  • 2 l r w:1≤l≤r≤n1\le l\le r\le n,1≤w≤10101\le w\le10^{10}。
  • 3 k p q:1≤k≤n1\le k\le n,1≤p≤q≤10101\le p\le q\le10^{10}。

输入只有一组数据。

输出格式

对于每个第三类操作,输出一行一个整数,表示所查询的元素之和。

如果没有第三类操作,则不输出任何内容。空栈上的出栈不会抵消未来压入的元素。

原样例

输入:

4 8
1 1 3 3 2
1 2 4 2 1
3 1 2 4
3 2 2 4
2 2 3 1
2 1 2 2
3 1 1 1
3 2 2 3

输出:

4
5
2
2