CF1872E.Data Structures Fan

You are given an array of integers $a_1, a_2, \ldots, a_n$, as well as a binary string$^{\dagger}$ $s$ consisting of $n$ characters.

Augustin is a big fan of data structures. Therefore, he asked you to implement a data structure that can answer $q$ queries. There are two types of queries:

• "1 $l$ $r$" ($1\le l \le r \le n$) — replace each character $s_i$ for $l \le i \le r$ with its opposite. That is, replace all $\texttt{0}$ with $\texttt{1}$ and all $\texttt{1}$ with $\texttt{0}$.
• "2 $g$" ($g \in {0, 1}$) — calculate the value of the bitwise XOR of the numbers $a_i$ for all indices $i$ such that $s_i = g$. Note that the $\operatorname{XOR}$ of an empty set of numbers is considered to be equal to $0$.

Please help Augustin to answer all the queries!

For example, if $n = 4$, $a = [1, 2, 3, 6]$, $s = \texttt{1001}$, consider the following series of queries:

1. "2 $0$" — we are interested in the indices $i$ for which $s_i = \tt{0}$, since $s = \tt{1001}$, these are the indices $2$ and $3$, so the answer to the query will be $a_2 \oplus a_3 = 2 \oplus 3 = 1$.
2. "1 $1$ $3$" — we need to replace the characters $s_1, s_2, s_3$ with their opposites, so before the query $s = \tt{1001}$, and after the query: $s = \tt{0111}$.
3. "2 $1$" — we are interested in the indices $i$ for which $s_i = \tt{1}$, since $s = \tt{0111}$, these are the indices $2$, $3$, and $4$, so the answer to the query will be $a_2 \oplus a_3 \oplus a_4 = 2 \oplus 3 \oplus 6 = 7$.
4. "1 $2$ $4$" — $s = \tt{0111}$ $\to$ $s = \tt{0000}$.
5. "2 $1$" — $s = \tt{0000}$, there are no indices with $s_i = \tt{1}$, so since the $\operatorname{XOR}$ of an empty set of numbers is considered to be equal to $0$, the answer to this query is $0$.

$^{\dagger}$ A binary string is a string containing only characters $\texttt{0}$ or $\texttt{1}$.

给你一个整数数组 $a_1, a_2, \ldots, a_n$，以及一个由 $n$ 个字符组成的二进制字符串$^{\dagger}$ $s$。

奥古斯丁是一位数据结构爱好者。因此，他请你实现一种数据结构，以回答 $q$ 个查询。查询共分两类：

• “1 $l$ $r$”（其中 $1\le l \le r \le n$）——将所有满足 $l \le i \le r$ 的字符 $s_i$ 替换为其相反字符。即：将所有 $\texttt{0}$ 替换为 $\texttt{1}$，所有 $\texttt{1}$ 替换为 $\texttt{0}$。
• “2 $g$”（其中 $g \in \{0, 1\}$）——计算所有满足 $s_i = g$ 的下标 $i$ 对应的 $a_i$ 的按位异或值。注意：空集合的 $\operatorname{XOR}$ 值定义为 $0$。

请帮助奥古斯丁回答所有查询！

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

1. “2 $0$” —— 我们关注满足 $s_i = \tt{0}$ 的下标 $i$；由于 $s = \tt{1001}$，这些下标为 $2$ 和 $3$，因此该查询的答案为 $a_2 \oplus a_3 = 2 \oplus 3 = 1$。
2. “1 $1$ $3$” —— 我们需将字符 $s_1, s_2, s_3$ 替换为其相反字符；查询前 $s = \tt{1001}$，查询后变为 $s = \tt{0111}$。
3. “2 $1$” —— 我们关注满足 $s_i = \tt{1}$ 的下标 $i$；由于 $s = \tt{0111}$，这些下标为 $2$、$3$ 和 $4$，因此该查询的答案为 $a_2 \oplus a_3 \oplus a_4 = 2 \oplus 3 \oplus 6 = 7$。
4. “1 $2$ $4$” —— $s = \tt{0111}$ $\to$ $s = \tt{0000}$。
5. “2 $1$” —— $s = \tt{0000}$，不存在满足 $s_i = \tt{1}$ 的下标，因此根据空集合的 $\operatorname{XOR}$ 值为 $0$ 的约定，该查询的答案为 $0$。

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

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case description contains an integer $n$ ($1 \le n \le 10^5$) — the length of the array.

The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The third line of the test case contains the binary string $s$ of length $n$.

The fourth line of the test case contains one integer $q$ ($1 \le q \le 10^5$) — the number of queries.

The subsequent $q$ lines of the test case describe the queries. The first number of each query, $tp \in {1, 2}$, characterizes the type of the query: if $tp = 1$, then $2$ integers $1 \le l \le r \le n$ follow, meaning that the operation of type $1$ should be performed with parameters $l, r$, and if $tp = 2$, then one integer $g \in {0, 1}$ follows, meaning that the operation of type $2$ should be performed with parameter $g$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and also that the sum of $q$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $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$，表示需以参数 $l, r$ 执行类型 $1$ 的操作；若 $tp = 2$，则其后跟随一个整数 $g \in \{0, 1\}$，表示需以参数 $g$ 执行类型 $2$ 的操作。

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

For each test case, and for each query of type $2$ in it, output the answer to the corresponding query.

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

Let's analyze the first test case:

1. "2 $0$" — we are interested in the indices $i$ for which $s_i = \tt{0}$, since $s = \tt{01000}$, these are the indices $1, 3, 4$, and $5$, so the answer to the query will be $a_1 \oplus a_3 \oplus a_4 \oplus a_5 = 1 \oplus 3 \oplus 4 \oplus 5 = 3$.
2. "2 $1$" — we are interested in the indices $i$ for which $s_i = \tt{1}$, since $s = \tt{01000}$, the only suitable index is $2$, so the answer to the query will be $a_2 = 2$.
3. "1 $2$ $4$" — we need to replace the characters $s_2, s_3, s_4$ with their opposites, so before the query $s = \tt{01000}$, and after the query: $s = \tt{00110}$.
4. "2 $0$" — we are interested in the indices $i$ for which $s_i = \tt{0}$, since $s = \tt{00110}$, these are the indices $1, 2$, and $5$, so the answer to the query will be $a_1 \oplus a_2 \oplus a_5 = 1 \oplus 2 \oplus 5 = 6$.
5. "2 $1$" — we are interested in the indices $i$ for which $s_i = \tt{1}$, since $s = \tt{00110}$, these are the indices $3$ and $4$, so the answer to the query will be $a_3 \oplus a_4 = 3 \oplus 4 = 7$.
6. "1 $1$ $3$" — $s = \tt{00110}$ $\to$ $s = \tt{11010}$.
7. "2 $1$" — we are interested in the indices $i$ for which $s_i = \tt{1}$, since $s = \tt{11010}$, these are the indices $1, 2$, and $4$, so the answer to the query will be $a_1 \oplus a_2 \oplus a_4 = 1 \oplus 2 \oplus 4 = 7$.

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

1. “2 $0$” — 我们关注满足 $s_i = \tt{0}$ 的下标 $i$；由于 $s = \tt{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 = \tt{1}$ 的下标 $i$；由于 $s = \tt{01000}$，唯一满足条件的下标是 $2$，因此该查询的答案为 $a_2 = 2$。
3. “1 $2$ $4$” — 我们需要将字符 $s_2, s_3, s_4$ 替换为其相反字符；查询前 $s = \tt{01000}$，查询后变为 $s = \tt{00110}$。
4. “2 $0$” — 我们关注满足 $s_i = \tt{0}$ 的下标 $i$；由于 $s = \tt{00110}$，这些下标为 $1, 2$ 和 $5$，因此该查询的答案为 $a_1 \oplus a_2 \oplus a_5 = 1 \oplus 2 \oplus 5 = 6$。
5. “2 $1$” — 我们关注满足 $s_i = \tt{1}$ 的下标 $i$；由于 $s = \tt{00110}$，这些下标为 $3$ 和 $4$，因此该查询的答案为 $a_3 \oplus a_4 = 3 \oplus 4 = 7$。
6. “1 $1$ $3$” — $s = \tt{00110}$ $\to$ $s = \tt{11010}$。
7. “2 $1$” — 我们关注满足 $s_i = \tt{1}$ 的下标 $i$；由于 $s = \tt{11010}$，这些下标为 $1, 2$ 和 $4$，因此该查询的答案为 $a_1 \oplus a_2 \oplus a_4 = 1 \oplus 2 \oplus 4 = 7$。