给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$,以及一个由 $$$n$$$ 字符组成的二进制字符串$$$^{\dagger}$$$ $$$s$$$。
Augustin 是数据结构的忠实粉丝。因此,他要求你实现一个可以回答 $$$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\}$$$) - 计算所有索引 $$$i$$$ 的数字 $$$a_i$$$ 按位异或的值,使得 $$$s_i = g$$$。请注意,空数字集的 $$$\operatorname{XOR}$$$ 被视为等于 $$$0$$$。
请帮助奥古斯丁回答所有疑问!
例如,如果 $$$n = 4$$$、$$$a = [1, 2, 3, 6]$$$、$$$s = \texttt{1001}$$$,请考虑以下一系列查询:
1. "2 $$$0$$$" - 我们感兴趣的是索引 $$$i$$$,其中 $$$s_i = \tt{0}$$$,因为 $$$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$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{1}$$$,因为 $$$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}$$$ 的字符串。
输入
输入的第一行包含一个整数 $$$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$$$,则后面跟着 $$$2$$$ 整数 $$$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
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
输出 #1
3 2 6 7 7 11 7 0 0 16430827 47
注意
我们来分析第一个测试用例:
1. "2 $$$0$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{0}$$$,因为 $$$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$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{0}$$$,因为 $$$s = \tt{00110}$$$,这些是索引 $$$1、2$$$ 和 $$$5$$$,因此查询的答案将为 $$$a_1 \oplus a_2 \oplus a_5 = 1 \oplus 2 \oplus 5 = 6$$$。
5. "2 $$$1$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{1}$$$,因为 $$$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$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{1}$$$,因为 $$$s = \tt{11010}$$$,这些是索引 $$$1、2$$$ 和 $$$4$$$,因此查询的答案将为 $$$a_1 \oplus a_2 \oplus a_4 = 1 \oplus 2 \oplus 4 = 7$$$。