You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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}$$$.

## Input Format
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 Format
For each test case, and for each query of type $$$2$$$ in it, output the answer to the corresponding query.

## Examples
```input
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
```
```output
3 2 6 7 7 
11 7 
0 0 
16430827 
47
```

## Note
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$$$.

Now solve the problem and return the code.