有 $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$ 个元素在栈中不存在，则视为 $0$。

请帮助我处理这 $m$ 次操作。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)。

接下来的 $m$ 行，每行描述一个操作，格式如下：

• 1 l r x y ($1 \le l \le r \le n, 1 \le x, y \le 10^5$)：在编号位于区间 $[l, r]$ 内的每个栈中压入 $x$ 个 $y$。
• 2 l r w ($1 \le l \le r \le n, 1 \le w \le 10^{10}$)：对编号位于区间 $[l, r]$ 内的每个栈执行 $w$ 次弹出操作。
• 3 k p q ($1 \le k \le n, 1 \le p \le q \le 10^{10}$)：查询编号为 $k$ 的栈中，从底部开始第 $p$ 个元素到第 $q$ 个元素的元素之和。

输出格式

对于每个查询，输出一行，包含一个整数，表示答案。

样例

样例输入 1

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

样例输出 1

4
5
2
2