Problem
Natalya Korshunova sente muita falta de Grigory Melekhov e quer voltar para ele. Mas, infelizmente, Grigory ama Aksinya, então Natalya decidiu provar para sua amada que ela é melhor do que ela.
Para fazer isso, Natalia foi até Grigory e declarou que poderia resolver qualquer problema, qualquer que fosse o que ele sugerisse. Melekhov aceitou o desafio.
Grigory dá a Natalia um array A que consiste em n inteiros não negativos. Em seguida, ele pede que ela execute operações q do mesmo tipo, consistindo no seguinte: "Dados os números l, r e k . Além disso, para cada índice i de l a r, o número k é substituído em vez do número A i e é considerado um bit a bit exclusivo “ou” todos os números no segmento \([l;r]\), após o qual o número Aiº lugar novamente >i".
Assim, existem \(r – l + 1\) substituições independentes que não alteram a matriz e, portanto, \( r – l + 1\) resulta em um bit a bit exclusivo “ou”. Natalia precisa dizer a Grigory um bitwise exclusivo “ou” todos os resultados das substituições (para entender melhor, veja os exemplos).
Ajude Natalia Korshunova a lidar com esta tarefa! Então Gregory definitivamente voltará para ela!
Entrada
A primeira linha é um inteiro n (\(1 <= n <= 10^5\)) – número de elementos da matriz.
A segunda linha contém n inteiros não negativos que não excedem \(10^8\).
A terceira linha é um inteiro q (\(1 <= q <= 10^5\)) – número de solicitações.
O seguinte contém q linhas, cada uma contendo 3 números inteiros: l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).
Saída
Você precisa gerar respostas
q para cada consulta em uma linha separada por um espaço.
Exemplos
| # |
Entrada |
Saída |
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
Explicação
Primeiro pedido:
1) 7 ⊕ 2⊕ 3 = 6
2) 1 ⊕ 7⊕ 3 = 5
3) 1 ⊕ 2⊕ 7 = 4
6 ⊕ 5 &o mais; 4 = 7
Resposta: 7.
Segundo pedido:
1) 10 ⊕ 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
Resposta: 1.