Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Наталья Коршунова очень скучает по Григорию Мелехову и хочет вернуться к нему. Но, к сожалению, Григорий любит Аксинью, поэтому Наталья решила доказать любимому, что она лучше нее.
Для этого Наталья отправилась к Григорию и заявила, что она может решить любую задачу, какую бы он ни предложил. Мелехов принял вызов.
Григорий дает Наталье массив A, состоящий из n целых неотрицательных чисел. Затем он просит ее сделать q однотипных операций, заключающихся в следующем: Даны числа l, r и k. Далее для каждого индекса i от l до r происходит подстановка числа k вместо числа Ai и считается побитовое исключающее “или” всех чисел на отрезке [l;r], после чего на iое место опять возвращается число Ai. Таким образом, происходит r – l + 1 независимых подстановок, не меняющих массив, и соответственно r – l + 1 результатов побитового исключающего “или”. Наталье необходимо сообщить Григорию побитовое исключающее “или” всех результатов подстановок (для лучшего понимания ознакомьтесь с примерами).
Помогите Наталье Коршуновой справиться с этой задачей! Тогда Григорий точно вернется к ней!
Входные данные
В первой строке дано целое число n (1 <= n <= 10^5) – количество элементов массива.
Во второй строке содержится n целых неотрицательных чисел, не превышающих по значению 10^8.
В третьей строке дано целое число q (1 <= q <= 10^5) – количество запросов.
Далее содержится q строк, в каждой из которых содержится 3 целых числа: l, r, k (1 <= l <= r <= n, 0 <= k <= 10^8).
Выходные данные
Вам необходимо вывести q ответов на каждый запрос в одной строке через пробел.
|
Ввод |
Вывод |
|
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
Пояснение:
Первый запрос:
1) 7 ⊕ 2 ⊕ 3 = 6
2) 1 ⊕ 7 ⊕ 3 = 5
3) 1 ⊕ 2 ⊕ 7 = 4
6 ⊕ 5 ⊕ 4 = 7
Ответ: 7
Второй запрос:
1) 10 ⊕ 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
Ответ: 1
(с) Курбатов Е., 2018