有 $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\le n,m\le 10^5,1\le x,y\le 10^5,1\le w\le 10^{10},1\le p\le q\le 10^{10}$。
- Subtask1(18pts): $n,m\le 5000$。
- Subtask2(21pts): 保证不存在 $2$ 操作。
- Subtask3(16pts): 对于所有的操作 $1$，保证 $y=1$。
- Subtask4(24pts): 对于所有的 $3$ 操作，保证 $p=1,q=10^{10}$。
- Subtask5(21pts): 无特殊限制。