There are $n$ stacks, numbered from $1$ to $n$. There are $m$ operations of three types:

• $1\ l\ r\ x\ y$: Push $x$ copies of $y$ onto each stack with an index in the range $[l, r]$.
• $2\ l\ r\ w$: Perform the pop operation $w$ times on each stack with an index in the range $[l, r]$. If a stack is empty, do nothing; otherwise, remove the top element.
• $3\ k\ p\ q$: Query the sum of elements from the $p$-th to the $q$-th position (inclusive) in stack $k$, counting from the bottom. If the $i$-th element does not exist in the stack, treat it as $0$.

Input

The first line contains two integers $n$ and $m$.

Each of the next $m$ lines describes an operation in the following format:

• $1\ l\ r\ x\ y$: Push $x$ copies of $y$ onto each stack with an index in the range $[l, r]$.
• $2\ l\ r\ w$: Perform the pop operation $w$ times on each stack with an index in the range $[l, r]$.
• $3\ k\ p\ q$: Query the sum of elements from the $p$-th to the $q$-th position in stack $k$.

Output

For each query, output a single integer representing the answer.

Examples

Input 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

Output 1

4
5
2
2

Subtasks

For all data, $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}$.

• Subtask 1 (18 pts): $n, m \le 5000$.
• Subtask 2 (21 pts): Guaranteed that no type $2$ operations occur.
• Subtask 3 (16 pts): For all type $1$ operations, $y=1$ is guaranteed.
• Subtask 4 (24 pts): For all type $3$ operations, $p=1, q=10^{10}$ is guaranteed.
• Subtask 5 (21 pts): No special restrictions.