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