D. Xor them all!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность целых чисел a длины n и несколько запросов двух типов:

1. ! i x (1 ≤ i ≤ n, 0 ≤ x < 230) — заменить ai на число x;

2. ? l r (1 ≤ l ≤ r ≤ n) — посчитать последние девять цифр величины , где  — операция побитового исключающего или, в современных языках программирования обозначается как xor или .

Входные данные

Первая строка содержит целое число n — длину последовательности. Вторая строка содержит n целых чисел, разделённых пробелами — элементы последовательности. В третьей строке содержится число m - количество запросов. Следующие m строк содержат запросы в формате, описанном выше. 1 ≤ n, m ≤ 105, 0 ≤ ai < 230.

Выходные данные

На каждый запрос второго типа выведите в отдельной строке ответ на этот запрос.

Примеры
Входные данные
4
1 2 3 4
8
? 1 3
? 2 4
? 1 4
! 2 0
? 1 3
! 4 1
? 1 4
? 2 3
Выходные данные
0
5
18
2
7
0