题目描述

给定一个长为 $n$ 的序列 $a$，有两种操作，共 $m$ 次：

1. 给定 $l$ $r$ $x$，对于所有 $i$ 满足 $l\le i\le r$ 且 $a_i \neq x$，$a_i\leftarrow a_i-x$。
2. 给定 $l$ $r$，求对于所有 $i$ 满足 $l\le i\le r$ 且 $a_i\neq 0$，$a_i$ 的和。

输入格式

第一行两个数 $n,m$。

第二行 $n$ 个用空格隔开的数表示序列 $a$。

之后 $m$ 行，每行三个或四个数：

若输入为 1 l r x，则表示对区间 $[l,r]$ 进行一次 $1$ 操作，若输入为 2 l r，则表示对区间 $[l,r]$ 进行一次 $2$ 操作。

本题强制在线，所有输入的 $l,r,x$ 均需要异或 $lastans$，其定义为上一次询问操作得到的答案对 $2^{20}$ 取模后的值，若之前没有询问操作，则为 $0$。

输出格式

对每个 $2$ 操作，输出一行一个数表示答案对 $2^{64}$ 取模后的结果。

输入输出样例 #1

输入 #1

10 10
0 1 2 3 4 5 6 7 8 9
1 5 10 5
2 1 10
1 23 29 23
2 21 19
1 1048573 1048570 1048574
2 1048573 1048566
1 1048573 1048569 1048575
2 1048575 1048564
1 1048572 1048567 1048572
2 1048572 1048567

输出 #1

20
18446744073709551615
18446744073709551614
18446744073709551613
18446744073709551606

说明/提示

对于 $5\%$ 的数据，$n,m\le 1000$。

对于 $30\%$ 的数据，$n,m\le 5\times10^4$。

对于另外 $20\%$ 的数据，$l=1,r=n$。

对于另外 $20\%$ 的数据，$x=1$。

对于 $100\%$ 的数据 $1\le n,m \le 5\times10^5, 0\le a_i, x \le10^9$。