← Home 
write a go solution for 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<=l<=r<=n) — replace each character s_i for l<=i<=r with its opposite. That is, replace all texttt0 with texttt1 and all texttt1 with texttt0.
- "2 g" (gin0,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 operatornameXOR 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=texttt1001, consider the following series of queries:

1. "2 0" — we are interested in the indices i for which s_i=tt0, since s=tt1001, these are the indices 2 and 3, so the answer to the query will be a_2oplusa_3=2oplus3=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=tt1001, and after the query: s=tt0111.
3. "2 1" — we are interested in the indices i for which s_i=tt1, since s=tt0111, these are the indices 2, 3, and 4, so the answer to the query will be a_2oplusa_3oplusa_4=2oplus3oplus6=7.
4. "1 2 4" — s=tt0111 to s=tt0000.
5. "2 1" — s=tt0000, there are no indices with s_i=tt1, so since the operatornameXOR 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 texttt0 or texttt1.

Input Format:
The first line of the input contains one integer t (1<=t<=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<=n<=10^5) — the length of the array.

The second line of the test case contains n integers a_1,a_2,...,a_n (1<=a_i<=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<=q<=10^5) — the number of queries.

The subsequent q lines of the test case describe the queries. The first number of each query, tpin1,2, characterizes the type of the query: if tp=1, then 2 integers 1<=l<=r<=n follow, meaning that the operation of type 1 should be performed with parameters l,r, and if tp=2, then one integer gin0,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.

Note:
Let's analyze the first test case:

1. "2 0" — we are interested in the indices i for which s_i=tt0, since s=tt01000, these are the indices 1,3,4, and 5, so the answer to the query will be a_1oplusa_3oplusa_4oplusa_5=1oplus3oplus4oplus5=3.
2. "2 1" — we are interested in the indices i for which s_i=tt1, since s=tt01000, 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=tt01000, and after the query: s=tt00110.
4. "2 0" — we are interested in the indices i for which s_i=tt0, since s=tt00110, these are the indices 1,2, and 5, so the answer to the query will be a_1oplusa_2oplusa_5=1oplus2oplus5=6.
5. "2 1" — we are interested in the indices i for which s_i=tt1, since s=tt00110, these are the indices 3 and 4, so the answer to the query will be a_3oplusa_4=3oplus4=7.
6. "1 1 3" — s=tt00110 to s=tt11010.
7. "2 1" — we are interested in the indices i for which s_i=tt1, since s=tt11010, these are the indices 1,2, and 4, so the answer to the query will be a_1oplusa_2oplusa_4=1oplus2oplus4=7.. Output only the code with no comments, explanation, or additional text.