Существует бесконечная в левую, правую и верхнюю стороны сетка ячеек (существуют все ячейки с координатами $(x, y)$, где $x \in \mathbb{Z}, y \ge 0$). Изначально все ячейки белые. Вам необходимо обработать $q$ запросов двух типов:

1. $y_i$ $l_i$ $r_i$: закрасить все ячейки $(x, y_i)$ для $l_i \le x \le r_i$ в черный цвет. Если ячейка уже черная, её цвет не меняется.
2. $l_i$ $r_i$: рассмотреть все ячейки с координатой $x$ на отрезке $[l_i; r_i]$. Найти самую высокую ячейку такую, что все ячейки прямо под ней являются черными. Формально, вам нужно найти максимальное $h$ такое, что $\exists x \in [l_i; r_i] \forall y \in [0; h)$ ячейка $(x, y)$ является черной.

Чтобы обеспечить обработку запросов в режиме онлайн, они зашифрованы с использованием ответов на предыдущие запросы.

Входные данные

Первая строка содержит одно целое число $q$ ($1 \le q \le 10^5$) — количество запросов для обработки. Следующие $q$ строк содержат зашифрованные описания запросов. Пусть $S$ — сумма ответов на все запросы второго типа, обработанные к настоящему моменту. Каждое описание отформатировано либо как «1 $(y_i \oplus S)$ $(l_i \oplus S)$ $(r_i \oplus S)$», либо как «2 $(l_i \oplus S)$ $(r_i \oplus S)$». Гарантируется, что $0 \le y_i \le 2 \cdot 10^5$, $0 \le l_i \le r_i \le 2 \cdot 10^5$. Заметьте, что гарантии даны для параметров после расшифровки, числа во входных данных могут не помещаться в 32-битные целые числа. Не забудьте прибавлять новый ответ к $S$ после каждого запроса второго типа.

Выходные данные

Выведите ответы на все запросы второго типа на отдельных строках.

Примеры

Входные данные 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

Выходные данные 1

1
0
2
2

Примечание

Рисунок 1. Иллюстрация операций над сеткой и запросов.