Вам дан массив целых чисел \(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}\), рассмотрим серию запросов:
- «2 \(0\)» — нас интересуют индексы \(i\), для которых \(s_i = \tt{0}\), так как \(s = \tt{1001}\) — это индексы \(2\) и \(3\), а значит, ответом на запрос будет \(a_2 \oplus a_3 = 2 \oplus 3 = 1\).
- «1 \(1\) \(3\)» — нужно заменить символы \(s_1, s_2, s_3\) на противоположные, таким образом до запроса \(s = \tt{1001}\), а после запроса: \(s = \tt{0111}\).
- «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\).
- «1 \(2\) \(4\)» — \(s = \tt{0111}\) \(\to\) \(s = \tt{0000}\).
- «2 \(1\)» — \(s = \tt{0000}\), индексов с \(s_i = \tt{1}\) нет, а значит, так как \(\operatorname{XOR}\) от пустого набора чисел считается равным \(0\), ответ на этот запрос: \(0\).
\(^{\dagger}\) Бинарная строка — это строка, содержащая только символы \(\texttt{0}\) или \(\texttt{1}\).
Выходные данные
Для каждого набора входных данных, и для каждого запроса типа \(2\) в нём, выведите ответ на соответствующий запрос.
Примечание
Разберём первый набор входных данных примера:
- «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 \(1\)» — нас интересуют индексы \(i\), для которых \(s_i = \tt{1}\), так как \(s = \tt{01000}\) — единственный подходящий индекс: \(2\), а значит, ответом на запрос будет \(a_2 = 2\).
- «1 \(2\) \(4\)» — нужно заменить символы \(s_2, s_3, s_4\) на противоположные, таким образом до запроса \(s = \tt{01000}\), а после запроса: \(s = \tt{00110}\).
- «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\).
- «2 \(1\)» — нас интересуют индексы \(i\) для которых \(s_i = \tt{1}\), так как \(s = \tt{00110}\) — это индексы \(3\) и \(4\), а значит ответом на запрос будет \(a_3 \oplus a_4 = 3 \oplus 4 = 7\).
- «1 \(1\) \(3\)» — \(s = \tt{00110}\) \(\to\) \(s = \tt{11010}\).
- «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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3 2 6 7 7
11 7
0 0
16430827
47
|