E. Фанат структур данных
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$, а также бинарная строка$$$^{\dagger}$$$ $$$s$$$, состоящая из $$$n$$$ символов

Августин — большой фанат структур данных. Поэтому он попросил вас реализовать структуру данных, способную ответить на $$$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\}$$$) — вычислить значение побитового XORа чисел $$$a_i$$$ по всем индексам $$$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$$$).

Третья строка набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$.

Четвёртая строка набора входных данных содержит целое число $$$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$$$ в нём, выведите ответ на соответствующий запрос.

Пример
Входные данные
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
Примечание

Разберём первый набор входных данных примера:

  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$$$» — нас интересуют индексы $$$i$$$, для которых $$$s_i = \tt{1}$$$, так как $$$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$$$.