题目描述

你有一个 $n$ 行 $m$ 列的网格，每个格子可以被染黑或染白，初始每个格子均为白色。定义第 $i$ 行的美观程度为最大的 $x$，满足对于所有 $1 \le j \le x$，第 $i$ 行的第 $j$ 个格子的颜色是黑色。

你需要对这个网格执行 $m$ 次操作。操作有以下四种：

1. 给定三个整数 $l, r, x$，表示把第 $x$ 列的第 $l$ 到第 $r$ 个格子染黑。
2. 给定三个整数 $l, r, x$，表示把第 $x$ 列的第 $l$ 到第 $r$ 个格子染白。
3. 给定三个整数 $l, r, v$，你需要把第 $l$ 到第 $r$ 行中美观程度最小的行的权值加上 $v$，如有多行均为最小则对每行都加 $v$。
4. 给定两个整数 $l, r$，你需要输出第 $l$ 到第 $r$ 行的权值之和，对 $2^{64}$ 取模。

每行初始权值为 $0$。

输入格式

第一行包含两个整数 $n, m$。

接下来 $m$ 行，每行第一个正整数 $op_i$ 表示操作编号。

• 对于 $op_i = 1$ 或 $op_i = 2$，后面紧跟三个正整数 $l_i, r_i, x_i$，表示执行上述对应操作。
• 对于 $op_i = 3$，后面紧跟三个整数 $l_i, r_i, v_i$，表示执行上述对应操作。
• 对于 $op_i = 4$，后面紧跟两个整数 $l_i, r_i$，表示询问这个区间的权值之和对 $2^{64}$ 取模的值。

输出格式

若干行，对于每个 $op_i = 4$ 输出其答案。

样例

输入

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

输出

1
1
2

数据范围与提示

对于 $100\%$ 的数据：

• $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\times 10^5)$
• $0 \le v_i < 2^{64}$

本题采用子任务捆绑测试。

• $\text{subtask1}$ ($10$ pts)：保证 $1 \le n, m \le 1000$。
• $\text{subtask2}$ ($15$ pts)：保证 $x_i = 1$。
• $\text{subtask3}$ ($15$ pts)：保证 $1 \le x_i \le 10$。
• $\text{subtask4}$ ($20$ pts)：保证 $op_i = 3$ 和 $op_i = 4$ 的操作一定出现在所有 $op_i = 1$ 和 $op_i = 2$ 的操作之后。
• $\text{subtask5}$ ($10$ pts)：保证 $1 \le n, m \le 40000$。
• $\text{subtask6}$ ($30$ pts)：无特殊性质。