Code Submission Evaluation System Login

IOI-leiri 2016

Treap VIII


Task | Statistics


CSES - Treap VIIICSES - Treap VIII

Time limit:2.50 s Memory limit:2048 MB

Taulukko $0$ sisältää luvut $1, 2, \ldots, n$ tässä järjestyksessä. Saat syötteenä $q$ päivitystä siten, että $i$. päivitystä kuvaavat luvut $k_i$, $t_i$, $a_i$ ja $b_i$. Päivityksellä $i$ taulukosta $i - 1$ tehdään taulukko $i$ seuraavasti: Tässä $\oplus$ on biteittäinen XOR-operaattori. Voit olettaa, että $1\leq k_i\leq n$, $0\leq t_i\oplus x < i$, $1\leq a_i\oplus x\leq b_i\oplus x\leq n$ ja $c\leq d$. Tehtäväsi on selvittää taulukon $q$ sisältö.

Syöte

Syötteen ensimmäisellä rivillä on luvut $n$ ja $q$, taulukon koko ja päivitysten lukumäärä. Seuraavat $q$ riviä sisältävät päivitykset siten, että $i$. päivityksen rivillä on luvut $k_i$, $t_i$, $a_i$ ja $b_i$.

Tuloste

Tulosta yksi rivi, joka sisältää taulukon $q$ luvut välein eroteltuina.

Rajat
Esimerkki

Syöte:
8 10
8 8 10 15
3 6 1 14
3 7 1 5
5 6 2 14
8 7 6 2
8 3 6 0
5 2 0 11
4 6 2 7
7 4 14 0
3 13 9 14


Tuloste:
4 3 8 7 5 2 6 1