题目背景

请注意本题不同寻常的时空限制。

题目描述

在 $k$ 维空间中，有一个由整点构成的可重集 $S$（初始为空），$S$ 中每个点都有一个权值。记整点 $A$ 的第 $d$ 维坐标为 $x_d(A)$。

你需要维护三种操作：

• 操作一：向 $S$ 中插入点 $A$，权值为 $v$。
• 操作二：给定整点 $A$ 与整点 $B$，将满足 $C\in S$ 且 $\forall d\in\{1,2,\cdots,k\},x_d(A)\le x_d(C)\le x_d(B)$ 的所有整点 $C$ 的权值增加 $v$。
• 操作三：给定整点 $A$ 与整点 $B$，查询满足 $C\in S$ 且 $\forall d\in\{1,2,\cdots,k\},x_d(A)\le x_d(C)\le x_d(B)$ 的所有整点 $C$ 权值之和。

本题强制在线。

输入格式

第一行两个整数 $k,m$，表示空间维数与操作次数。

接下来 $m$ 行，每行若干个整数，描述一次操作：

• 若第一个整数为 $1$，接下来 $k+1$ 个整数 $x_1'(A),\cdots,x_k'(A),v'$，表示加密后的整点 $A$ 的坐标和权值。
• 若第一个整数为 $2$，接下来 $2k+1$ 个整数 $x_1'(A),\cdots,x_k'(A),x_1'(B),\cdots,x_k'(B),v'$，表示加密后的整点 $A$ 和 $B$ 的坐标以及权值增量。
• 若第一个整数为 $3$，接下来 $2k$ 个整数 $x_1'(A),\cdots,x_k'(A),x_1'(B),\cdots,x_k'(B)$，表示加密后的整点 $A$ 和 $B$ 的坐标。
• 对于加密后的数据 $a'$，原数据 $a$ 满足 $a=a'\oplus lst$，其中 $\oplus$ 为按位异或运算，$lst$ 为上次操作三的答案（初始为 $0$）。

输出格式

若干行，每行一个整数，依次为所有操作三的答案。

2 10
1 1 4 2
3 1 5 5 5
1 4 2 5
1 2 4 2
2 1 3 3 4 2
3 2 4 5 4
3 5 6 0 7
1 7 4 7
3 7 7 6 1
3 5 6 0 0

0
4
5
4
13

3 9
1 1 3 2 3
1 4 3 1 5
1 4 4 4 2
1 2 1 5 3
3 2 3 1 3 4 5
1 5 5 4 3
2 5 5 3 6 6 6 1
3 1 2 1 4 5 5
3 9 9 9 15 15 14

0
10
6

提示

「样例解释 #1」

:::info[解密后的输入]

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

:::

最后一次询问的范围包含 $(1,4),(4,2),(2,4)$ 三个整点，他们的权值之和为 $(2+2)+5+(2+2)=13$。

---

「样例解释 #2」

:::info[解密后的输入]

3 9
1 1 3 2 3
1 4 3 1 5
1 4 4 4 2
1 2 1 5 3
3 2 3 1 3 4 5
1 5 5 4 3
2 5 5 3 6 6 6 1
3 1 2 1 4 5 5
3 3 3 3 5 5 4

:::

最后一次询问的范围包含 $(4,4,4),(5,5,4)$ 两个整点，他们的权值之和为 $2+(3+1)=6$。

---

「数据范围」

对于所有测试数据，保证：

• 操作一满足解密后的 $1\le x_i(A)\le 10^{18}$ 且 $1\le v\le 10^5$；
• 操作二满足解密后的 $1\le x_i(A)\le x_i(B)\le 10^{18}$ 且 $1\le v\le 10^5$；
• 操作三满足解密后的 $1\le x_i(A)\le x_i(B)\le 10^{18}$。

子任务	$k=$	$m\le$	特殊性质	分值
$1$	$2$	$1.5\times 10^5$	不含操作二	$25$
$2$	^		无
$3$		$10^5$	不含操作二
$4$	^		无

请注意 $\bm{k}$ 与 $\bm{m}$ 没有同时达到各自数据范围的上界。