题目描述

你有一个 $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$ 输出其答案。

样例一

input

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

output

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\times10^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)$：无特殊性质。

时间限制：$4\texttt{s}$

空间限制：$1024\texttt{MB}$