Code Submission Evaluation System Login

IOI-leiri 2016

Treap IV


Task | Statistics


CSES - Treap IVCSES - Treap IV

Time limit:4.00 s Memory limit:256 MB

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
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