DisneyLand

Cerință

Administrația DisneyLand a decis modernizarea sistemului de monitorizare. Rezervările și interogările sosesc acum în timp real, iar sistemul trebuie să ofere răspunsuri instantanee fără a cunoaște evenimentele viitoare.

Mai mult, pentru a proteja confidențialitatea datelor, coordonatele de timp din fișierul de intrare sunt criptate folosind răspunsul anterior.

Se primesc $M$ operațiuni de două tipuri:

• Tip 1 (Rezervare): Se adaugă un grup de $z$ copii prezent în intervalul $[x', y']$. Se dau $x_{in}, y_{in}, z_{in}$.
• Tip 2 (Interogare): Se cere numărul minim de paznici necesari la momentul de timp $t'$. Se dă $t_{in}$.

Fie $LastAns$ valoarea ultimului răspuns afișat (numărul de paznici de la ultima operație de tip 2). Inițial, $LastAns = 0$. Coordonatele reale se calculează astfel:

• Pentru Tip 1: $x = x_{in} \oplus LastAns$, $y = y_{in} \oplus LastAns$, $z = z_{in}$. Intervalul real de vizită este $[x', y']$, unde $x' = \min(x, y)$ și $y' = \max(x, y)$.
• Pentru Tip 2: $t' = t_{in} \oplus LastAns$.

Fiecare paznic poate supraveghea cel mult $k$ copii. La orice moment $t$, numărul de paznici trebuie să acopere integral numărul de copii prezenți.

Date de intrare

Fișierul disneyland.in conține pe prima linie numerele întregi $M$ și $k$.

Următoarele $M$ linii conțin descrierea operațiilor, fiecare linie având una dintre formele:

• $1 \ x_{in} \ y_{in} \ z_{in}$ (operație de tip 1 — rezervare);
• $2 \ t_{in}$ (operație de tip 2 — interogare)

Date de ieșire

Fișierul disneyland.out va conține răspunsul pentru fiecare operație de tip 2, pe câte o linie separată.

Restricții și precizări

• $1 \leq M \leq 200 \ 000$
• $0 \leq x_{in}, y_{in}, z_{in}, t_{in} \leq 10^{18}$
• $1 \leq k, x', y', t' \leq 10^9$
• $\oplus$ reprezintă operația pe biți XOR.
• Se garantează că toate valorile intermediare și răspunsurile finale se încadrează în tipul long long.

Exemplu

disneyland.in

4 3
1 4 8 5
2 5
1 1 5 4
2 7

disneyland.out

2
3

Explicație

În acest exemplu, $k=3$ (un paznic la maximum $3$ copii) și inițial $LastAns = 0$.

• Operația 1 (Tip 1 - Rezervare): Se citesc $x_{in}=4$, $y_{in}=8$, $z_{in}=5$. $x = 4 \oplus 0 = 4$, $y = 8 \oplus 0 = 8$. Intervalul real de vizită este $[4, 8]$ cu $5$ copii.
• Operația 2 (Tip 2 - Interogare): Se citește $t_{in}=5$. $t' = 5 \oplus 0 = 5$. La momentul $5$, este prezentă doar prima rezervare ($5 \in [4, 8]$). Sunt $5$ copii în total. Rezultatul este 2, deci $LastAns$ devine $2$.
• Operația 3 (Tip 1 - Rezervare): Se citesc $x_{in}=1$, $y_{in}=5$, $z_{in}=4$. $x = 1 \oplus 2 = 3$, $y = 5 \oplus 2 = 7$. Intervalul real de vizită este $[3, 7]$ cu $4$ copii.
• Operația 4 (Tip 2 - Interogare): Se citește $t_{in}=7$. $t' = 7 \oplus 2 = 5$. La momentul real $5$, sunt active ambele rezervări:
  • Prima rezervare: $5 \in [4, 8] \implies 5$ copii.
  • A doua rezervare: $5 \in [3, 7] \implies 4$ copii.
    Totalul de copii la momentul $5$ este $5 + 4 = 9$. Rezultatul este $3$, deci $LastAns$ devine $3$.