Problem
Natalya Korshunova realmente extraña a Grigory Melekhov y quiere volver con él. Pero, desafortunadamente, Grigory ama a Aksinya, por lo que Natalya decidió demostrarle a su amado que es mejor que ella.
Para hacer esto, Natalia acudió a Grigory y le declaró que podía resolver cualquier problema, independientemente de lo que él sugiriera. Melekhov aceptó el desafío.
Grigory le da a Natalia una matriz A que consta de n enteros no negativos. Luego le pide que realice operaciones q del mismo tipo, que consisten en lo siguiente: "Dados los números l, r y k . Además, para cada índice i de l a r, se sustituye el número k en lugar del número A i y se considera un “o” exclusivo bit a bit; todos los números en el segmento \([l;r]\), después de lo cual el número Aith place otra vez >i".
Por lo tanto, hay \(r – l + 1\) sustituciones independientes que no cambian la matriz y, en consecuencia, \( r – l + 1\) da como resultado un “o” exclusivo bit a bit. Natalia necesita decirle a Grigory un “o” todos los resultados de sustitución (para una mejor comprensión, consulte los ejemplos).
¡Ayuda a Natalia Korshunova a hacer frente a esta tarea! ¡Entonces Gregory definitivamente regresará con ella!
Entrada
La primera línea es un número entero n (\(1 <= n <= 10^5\)) – número de elementos de la matriz.
La segunda línea contiene n enteros no negativos que no excedan \(10^8\).
La tercera línea es un número entero q (\(1 <= q <= 10^5\)) – número de solicitudes.
Lo siguiente contiene líneas q, cada una con 3 números enteros: l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).
Salida
Debe generar respuestas
q para cada consulta en una línea separada por un espacio.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
Explicación
Primera solicitud:
1) 7 ⊕ 2+ 3 = 6
2) 1 ⊕ 7+ 3 = 5
3) 1 ⊕ 2+ 7 = 4
6 ⊕ 5 ⊕ 4 = 7
Respuesta: 7.
Segunda solicitud:
1) 10 ⊕ 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
Respuesta: 1.