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