Tehtävänäsi on ylläpitää järjestettyä lukutaulukkoa, johon tehdään seuraavanlaisia päivityksiä: Annetaan luvut i ja x. Lue kohdassa i oleva luku 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 i ja x. Voit olettaa, että päivityksen aikaan taulukossa on vähintään i 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^{62}

Esimerkki

Syöte:

10
1 4
1 3
3 9
1 13
4 14
2 1
1 11
7 12
7 13
2 1

Tuloste:

4
3
13
13
3
2
11
1
6
0