Istnieje nieskończona w lewo, w prawo i w górę siatka komórek (istnieją wszystkie komórki o współrzędnych $(x, y)$, gdzie $x \in \mathbb{Z}, y \ge 0$). Początkowo wszystkie komórki są białe. Musisz przetworzyć $q$ zapytań dwóch typów:

1. $y_i$ $l_i$ $r_i$: pomaluj wszystkie komórki $(x, y_i)$ dla $l_i \le x \le r_i$ na czarno. Jeśli komórka jest już czarna, jej kolor nie ulega zmianie.
2. $l_i$ $r_i$: rozważ wszystkie komórki o współrzędnej $x$ należącej do przedziału $[l_i, r_i]$. Znajdź najwyższą komórkę taką, że wszystkie komórki dokładnie pod nią są czarne. Formalnie, musisz znaleźć maksymalne $h$ takie, że $\exists x \in [l_i, r_i] \forall y \in [0, h)$ komórka $(x, y)$ jest czarna.

Aby wymusić przetwarzanie zapytań w trybie online, są one szyfrowane przy użyciu poprzednich odpowiedzi.

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $q$ ($1 \le q \le 10^5$) — liczbę zapytań do przetworzenia.

Kolejne $q$ linii zawiera zaszyfrowane opisy zapytań. Niech $S$ będzie sumą odpowiedzi na wszystkie dotychczas przetworzone zapytania drugiego typu.

Każdy opis ma format „1 $(y_i \oplus S)$ $(l_i \oplus S)$ $(r_i \oplus S)$” lub „2 $(l_i \oplus S)$ $(r_i \oplus S)$”. Gwarantuje się, że $0 \le y_i \le 2 \cdot 10^5$, $0 \le l_i \le r_i \le 2 \cdot 10^5$. Zauważ, że gwarancje dotyczą parametrów po odszyfrowaniu; liczby w wejściu mogą nie mieścić się w 32-bitowych liczbach całkowitych.

Nie zapomnij dodać nowej odpowiedzi do $S$ po każdym zapytaniu drugiego typu.

Wyjście

Wypisz odpowiedzi na wszystkie zapytania drugiego typu w osobnych liniach.

Przykład

Wejście 1

10
1 0 1 1
2 0 10
1 1 9 9
1 0 0 6
1 0 3 9
2 5 5
1 1 5 5
2 5 5
2 0 5
1 7 6 3

Wyjście 1

1
0
2
2

Uwagi

Poniższa tabela przedstawia proces przetwarzania zapytań z przykładu: