Data Structures Fan
Description
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:
- "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$.
- "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}$.
- "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$.
- "1 $2$ $4$" — $s = \tt{0111}$ $\to$ $s = \tt{0000}$.
- "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}$.
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$.
For each test case, and for each query of type $2$ in it, output the answer to the corresponding query.
Input
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$.
Output
For each test case, and for each query of type $2$ in it, output the answer to the corresponding query.
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
Note
Let's analyze the first test case:
- "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 $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$.
- "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}$.
- "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$.
- "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$.
- "1 $1$ $3$" — $s = \tt{00110}$ $\to$ $s = \tt{11010}$.
- "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$.