题目描述

给定一个整数数组 $a_1, a_2, \ldots, a_n$，以及一个长度为 $n$ 的二进制字符串 $s$（$^\dagger$）。

Augustin 非常喜欢数据结构，因此他让你实现一个数据结构来回答 $q$ 个查询。查询有两种类型：

• “1 $l$ $r$”（$1 \le l \le r \le n$）——将 $s$ 中第 $l$ 到第 $r$ 个字符全部取反。即，将所有 $\texttt{0}$ 变为 $\texttt{1}$，所有 $\texttt{1}$ 变为 $\texttt{0}$。
• “2 $g$”（$g \in \{0, 1\}$）——计算所有满足 $s_i = g$ 的 $a_i$ 的按位异或（bitwise XOR）值。注意，空集的 $\operatorname{XOR}$ 被认为是 $0$。

请你帮助 Augustin 回答所有的查询！

例如，若 $n = 4$，$a = [1, 2, 3, 6]$，$s = \texttt{1001}$，考虑如下查询序列：

1. “2 $0$”——我们关注 $s_i = \texttt{0}$ 的下标。此时 $s = \texttt{1001}$，对应下标为 $2$ 和 $3$，因此答案为 $a_2 \oplus a_3 = 2 \oplus 3 = 1$。
2. “1 $1$ $3$”——将 $s_1, s_2, s_3$ 取反，$s$ 由 $\texttt{1001}$ 变为 $\texttt{0111}$。
3. “2 $1$”——关注 $s_i = \texttt{1}$ 的下标。此时 $s = \texttt{0111}$，下标为 $2, 3, 4$，答案为 $a_2 \oplus a_3 \oplus a_4 = 2 \oplus 3 \oplus 6 = 7$。
4. “1 $2$ $4$”——$s = \texttt{0111}$ 变为 $s = \texttt{0000}$。
5. “2 $1$”——$s = \texttt{0000}$，没有 $s_i = \texttt{1}$ 的下标，因此答案为 $0$。

$^\dagger$ 二进制字符串指仅包含 $\texttt{0}$ 和 $\texttt{1}$ 的字符串。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

第三行包含一个长度为 $n$ 的二进制字符串 $s$。

第四行包含一个整数 $q$（$1 \le q \le 10^5$），表示查询的数量。

接下来的 $q$ 行，每行描述一个查询。每个查询的第一个数字 $tp \in \{1, 2\}$ 表示查询类型：若 $tp = 1$，则后面有两个整数 $1 \le l \le r \le n$，表示执行类型 $1$ 的操作，参数为 $l, r$；若 $tp = 2$，则后面有一个整数 $g \in \{0, 1\}$，表示执行类型 $2$ 的操作，参数为 $g$。

保证所有测试用例中 $n$ 的总和不超过 $10^5$，所有测试用例中 $q$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例中的每个类型 $2$ 的查询，输出对应的答案。

说明/提示

我们来分析第一个测试用例：

1. “2 $0$”——我们关注 $s_i = \texttt{0}$ 的下标。此时 $s = \texttt{01000}$，下标为 $1, 3, 4, 5$，答案为 $a_1 \oplus a_3 \oplus a_4 \oplus a_5 = 1 \oplus 3 \oplus 4 \oplus 5 = 3$。
2. “2 $1$”——关注 $s_i = \texttt{1}$ 的下标。此时 $s = \texttt{01000}$，只有下标 $2$，答案为 $a_2 = 2$。
3. “1 $2$ $4$”——将 $s_2, s_3, s_4$ 取反，$s$ 由 $\texttt{01000}$ 变为 $\texttt{00110}$。
4. “2 $0$”——关注 $s_i = \texttt{0}$ 的下标。此时 $s = \texttt{00110}$，下标为 $1, 2, 5$，答案为 $a_1 \oplus a_2 \oplus a_5 = 1 \oplus 2 \oplus 5 = 6$。
5. “2 $1$”——关注 $s_i = \texttt{1}$ 的下标。此时 $s = \texttt{00110}$，下标为 $3, 4$，答案为 $a_3 \oplus a_4 = 3 \oplus 4 = 7$。
6. “1 $1$ $3$”——$s = \texttt{00110}$ 变为 $s = \texttt{11010}$。
7. “2 $1$”——关注 $s_i = \texttt{1}$ 的下标。此时 $s = \texttt{11010}$，下标为 $1, 2, 4$，答案为 $a_1 \oplus a_2 \oplus a_4 = 1 \oplus 2 \oplus 4 = 7$。

由 ChatGPT 4.1 翻译

样例

5
5
1 2 3 4 5
01000
7
2 0
2 1
1 2 4
2 0
2 1
1 1 3
2 1
6
12 12 14 14 5 5
001001
3
2 1
1 2 4
2 1
4
7 7 7 777
1111
3
2 0
1 2 3
2 0
2
1000000000 996179179
11
1
2 1
5
1 42 20 47 7
00011
5
1 3 4
1 1 1
1 3 4
1 2 4
2 0

3 2 6 7 7 
11 7 
0 0 
16430827 
47