有 $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): 无特殊限制。