Problem
A Natalya Korshunova manca davvero Grigory Melekhov e vuole tornare da lui. Ma, sfortunatamente, Grigory ama Aksinya, quindi Natalya ha deciso di dimostrare alla sua amata che è migliore di lei.
Per fare questo, Natalia andò da Grigory e dichiarò che poteva risolvere qualsiasi problema, qualunque cosa suggerisse. Melekhov ha accettato la sfida.
Grigory dà a Natalia un array A composto da n numeri interi non negativi. Poi le chiede di eseguire operazioni q dello stesso tipo, costituite dalle seguenti: "Dati i numeri l, r e k . Inoltre, per ogni indice i da l a r, viene sostituito il numero k invece del numero A i ed è considerata un'esclusiva bit per bit “o” tutti i numeri nel segmento \([l;r]\), dopo di che il numero Aidi nuovo al 1° posto >i".
Quindi, ci sono \(r – l + 1\) sostituzioni indipendenti che non cambiano l'array, e di conseguenza \( r – l + 1\) risulta in un “o” esclusivo bit per bit. Natalia ha bisogno di dire a Grigory un'esclusiva “o” tutti i risultati di sostituzione (per una migliore comprensione, controlla gli esempi).
Aiuta Natalia Korshunova a far fronte a questo compito! Allora Gregory tornerà sicuramente da lei!
Input
La prima riga è un intero n (\(1 <= n <= 10^5\)) – numero di elementi dell'array.
La seconda riga contiene n interi non negativi che non superano \(10^8\).
La terza riga è un numero intero q (\(1 <= q <= 10^5\)) – numero di richieste.
Quanto segue contiene le righe q, ciascuna contenente 3 numeri interi: l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).
Uscita
Devi generare le risposte
q per ogni query su una riga separata da uno spazio.
Esempi
| # |
Input |
Uscita |
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
Spiegazione
Prima richiesta:
1) 7 ⊕ 2+ 3 = 6
2) 1 ⊕ 7+ 3 = 5
3) 1 ⊕ 2+ 7 = 4
6 ⊕ 5 ⊕ 4 = 7
Risposta: 7.
Seconda richiesta:
1) 10 ⊕ 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
Risposta: 1.