Problem
Natalya Korshunova manque vraiment à Grigory Melekhov et veut revenir vers lui. Mais, malheureusement, Grigory aime Aksinya, alors Natalya a décidé de prouver à sa bien-aimée qu'elle était meilleure qu'elle.
Pour ce faire, Natalia est allée voir Grigory et a déclaré qu'elle pouvait résoudre n'importe quel problème, quoi qu'il suggère. Melekhov a accepté le défi.
Grigory donne à Natalia un tableau A composé de n entiers non négatifs. Puis il lui demande d'effectuer des opérations q du même type, consistant à : "Étant donné les nombres l, r et k . De plus, pour chaque index i de l à r, le nombre k est substitué au nombre A i et est considéré comme un "ou" exclusif au niveau du bit ; tous les nombres du segment \([l;r]\), après quoi le nombre Ai à nouveau la ème place >i".
Ainsi, il existe des substitutions indépendantes \(r – l + 1\) qui ne modifient pas le tableau, et par conséquent \( r – l + 1\) donne un "ou" exclusif au niveau du bit. Natalia doit dire à Grigory un “ou” tous les résultats de substitution (pour une meilleure compréhension, consultez les exemples).
Aidez Natalia Korshunova à faire face à cette tâche ! Alors Gregory reviendra certainement vers elle !
Entrée
La première ligne est un entier n (\(1 <= n <= 10^5\)) – nombre d'éléments du tableau.
La deuxième ligne contient n entiers non négatifs ne dépassant pas \(10^8\).
La troisième ligne est un entier q (\(1 <= q <= 10^5\)) – nombre de requêtes.
Ce qui suit contient des lignes q, chacune contenant 3 entiers : l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).
Sortie
Vous devez afficher les réponses
q pour chaque requête sur une ligne séparées par un espace.
Exemples
| # |
Entrée |
Sortie |
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
7 1 |
Explication
Première demande :
1) 7 ⊕ 2⊕ 3 = 6
2) 1 ⊕ 7⊕ 3 = 5
3) 1 ⊕ 2⊕ 7 = 4
6 ⊕ 5 ⊕ 4 = 7
Réponse : 7.
Deuxième requête :
1) 10 ⊕ 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
Réponse : 1.