Tehtävänäsi on ylläpitää järjestettyä lukutaulukkoa, johon tehdään seuraavanlaisia päivityksiä: Annetaan luvut a, b ja x. Laske taulukon kohdissa a, a + 1, \ldots, b olevien lukujen summa modulo 2^{64} ja lisää sen ja luvun x biteittäinen XOR taulukkoon sellaiseen kohtaan, että taulukko pysyy järjestyksessä. Taulukossa on aluksi vain luku 0.

Syöte

Ensimmäisellä rivillä on luku n, päivitysten määrä. Seuraavat n riviä sisältävät päivitykset: jokaisella rivillä ovat päivitystä kuvaavat luvut a, b ja x. Voit olettaa, että a\leq b ja päivityksen aikaan taulukossa on vähintään b lukua.

Tuloste

Tulosta jokaista päivitystä kohti taulukkoon lisättävä luku omalla rivillään.

Rajat

• 1\leq n \leq 5\cdot 10^5
• 1\leq x < 2^{64}

Esimerkki

Syöte:

10
1 1 3
1 1 1
1 1 13
1 2 11
3 4 5
2 5 10
1 4 4
2 8 6
3 4 2
6 8 6

Tuloste:

3
1
13
10
8
28
8
65
9
38