题目描述

给定一个大小为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。有 $m$ 次操作，操作包含两种类型：

1. 1 l r：询问区间 $[l, r]$ 范围内的元素和，即 $a_l + a_{l+1} + \ldots + a_r$。
2. 2 l r x：将区间 $[l, r]$ 范围内的每个元素都异或上 $x$，即：$a_l \leftarrow a_l \oplus x, a_{l+1} \leftarrow a_{l+1} \oplus x, \ldots, a_r \leftarrow a_r \oplus x$。这个操作将会修改 $r - l + 1$ 个元素的值。

输入格式

输入的第一行包含一个整数 $n$，表示数列大小。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \le 10^6)$，两两之间以一个空格分隔，表示数列中的每个元素。

输入的第三行包含一个整数 $m(1 \le m \le 5 \cdot 10^4)$，表示操作次数。

接下来 $m$ 行，每行包含一个操作（1 l r 或 2 l r x）（$1 \le l \le r \le n, 1 \le x \le 10^6$）。

输出格式

对于每次询问操作 1 l r，输出一行，包含一个整数，表示区间 $[l, r]$ 范围内的元素和。

样例

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

26
22
0
34
11

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

38
28

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n, m \le 100$
• 对于 $100\%$ 的数据，$n \le 10^5, m \le 5 \cdot 10^5, 0 \le a_i \le 10^6, 1 \le x \le 10^6$