题目描述

给定一个长度为 $n$ 的整数数组 $A$，初始时所有元素都为 $0$。现在有 $m$ 次操作，操作分为两种类型：

1. 区间异或修改：给定三个整数 $l$、$r$ 和 $x$，将数组中从第 $l$ 个元素到第 $r$ 个元素（包括第 $l$ 和第 $r$ 个元素）的所有元素都异或上 $x$。
2. 区间异或和查询：给定两个整数 $l$ 和 $r$，查询数组中从第 $l$ 个元素到第 $r$ 个元素（包括第 $l$ 和第 $r$ 个元素）的所有元素的异或和。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 5*10^5$），分别表示数组的长度和操作的次数。 接下来 $m$ 行，每行表示一次操作。如果该行的第一个整数为 $1$，则表示区间异或修改操作，接下来有三个整数 $l$、$r$ 和 $x$（$1 \leq l \leq r \leq n$，$0 \leq x \leq 10^9$）；如果该行的第一个整数为 $2$，则表示区间异或和查询操作，接下来有两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）。

输出格式

对于每次区间异或和查询操作，输出一个整数，表示查询结果。

样例输入

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

样例输出

3
3

数据范围

• 对于 $30\%$ 的数据：$1 \leq n, m \leq 100$。
• 对于 $60\%$ 的数据：$1 \leq n, m \leq 10000$。
• 对于 $100\%$ 的数据：$1 \leq n, m \leq 5*10^5$，$0 \leq x \leq 10^9$。