You have an $n \times m$ grid where each cell can be colored black or white. Initially, all cells are white. The beauty of row $i$ is defined as the largest $x$ such that for all $1 \le j \le x$, the $j$-th cell in row $i$ is black.

You need to perform $m$ operations on this grid. The operations are as follows:

1. Given three integers $l, r, x$, color the cells in column $x$ from row $l$ to row $r$ black.
2. Given three integers $l, r, x$, color the cells in column $x$ from row $l$ to row $r$ white.
3. Given three integers $l, r, v$, add $v$ to the weight of every row in the range $[l, r]$ that has the minimum beauty among all rows in that range. If multiple rows have the same minimum beauty, add $v$ to each of them.
4. Given two integers $l, r$, output the sum of the weights of rows in the range $[l, r]$, modulo $2^{64}$.

The initial weight of each row is $0$.

Input

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

The next $m$ lines each start with an integer $op_i$ representing the operation type.

For $op_i = 1$ or $op_i = 2$, the operation is followed by three integers $l_i, r_i, x_i$, representing the corresponding operation described above.

For $op_i = 3$, the operation is followed by three integers $l_i, r_i, v_i$, representing the corresponding operation described above.

For $op_i = 4$, the operation is followed by two integers $l_i, r_i$, representing the query for the sum of weights in the range, modulo $2^{64}$.

Output

For each operation where $op_i = 4$, output the answer on a new line.

Examples

Input 1

3 5
1 2 2 1
3 1 3 1
4 1 1
4 1 2
4 1 3

Output 1

1
1
2

Constraints

For $100\%$ of the data, $1 \le n, m \le 3 \times 10^5$, $1 \le l_i \le r_i \le n$, $1 \le x_i \le \min(m, 1.5\times10^5)$, $0 \le v_i < 2^{64}$.

This problem uses subtask-based testing.

Subtask 1 ($10$ pts): $1 \le n, m \le 1000$.

Subtask 2 ($15$ pts): $x_i = 1$.

Subtask 3 ($15$ pts): $1 \le x_i \le 10$.

Subtask 4 ($20$ pts): All operations of type $op_i = 3$ and $op_i = 4$ occur after all operations of type $op_i = 1$ and $op_i = 2$.

Subtask 5 ($10$ pts): $1 \le n, m \le 40000$.

Subtask 6 ($30$ pts): No special properties.