Описание

Ограничение по времени: 1000 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Тихий Дон №3

Наталья Коршунова очень скучает по Григорию Мелехову и хочет вернуться к нему. Но, к сожалению, Григорий любит Аксинью, поэтому Наталья решила доказать любимому, что она лучше нее.
Для этого Наталья отправилась к Григорию и заявила, что она может решить любую задачу, какую бы он ни предложил. Мелехов принял вызов.
 
Григорий дает Наталье массив 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
 


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: