有 n 个栈,编号为 1 到 n。还有 m 次操作,操作有三种:
- 1 l r x y,表示给编号在区间 [l,r] 内的栈都压入 x 个 y。
- 2 l r w,表示让编号在区间 [l,r] 内的栈执行弹栈操作 w 次,这里弹栈操作是指,如果栈为空,则什么都不做;否则弹出栈顶。
- 3 k p q,表示查询编号为 k 的栈里从栈底开始数第 p 个到第 q 个元素之和,如果栈不存在第 i 个元素,则视为栈的第 i 个元素为 0。
输入格式
第一行两个整数 n,m。
接下来 m 行每行描述了一次操作,形如:
- 1 l r x y,给编号在区间 [l,r] 内的栈都压入 x 个 y。
- 2 l r w,让编号在区间 [l,r] 内的栈执行弹栈操作 w 次。
- 3 k p q,查询编号为 k 的栈里从栈底开始数第 p 个到第 q 个元素之和。
输出格式
对于每个询问,输出一个数表示答案。
样例数据
样例输入
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
子任务
对于全部的数据满足,1≤n,m≤105,1≤x,y≤105,1≤w≤1010,1≤p≤q≤1010。
- Subtask1(18pts): n,m≤5000。
- Subtask2(21pts): 保证不存在 2 操作。
- Subtask3(16pts): 对于所有的操作 1,保证 y=1。
- Subtask4(24pts): 对于所有的 3 操作,保证 p=1,q=1010。
- Subtask5(21pts): 无特殊限制。