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:

• Lue taulukon $i - 1$ kohdasta $k_i$ luku $x$.
• Lue taulukon $t_i\oplus x$ kohdista $a_i\oplus x$ ja $b_i\oplus x$ luvut $c$ ja $d$.
• Kopioi taulukko $i-1$ taulukoksi $i$ ja käännä taulukosta $i$ väli $c..d$ ympäri.

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

• $1\leq n\leq 10^5$
• $1\leq q\leq 10^5$

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