Busy Beaver любит задачи на структуры данных, но считает, что задачи на массивы с интервальными запросами — это скучно. Поэтому он придумал другой вид задачи на структуры данных, с мультимножествами!

Имеется последовательность $a_1, \dots, a_L$, где каждый элемент $a_i$ — это мультимножество положительных целых чисел. Изначально последовательность пуста, то есть $L=0$. Реализуйте следующие операции:

• 1 M K: Добавить в конец последовательности мультимножество, состоящее только из числа $M$, которое встречается $K$ раз.
• 2 X Y: Добавить в конец последовательности сумму $a_X$ и $a_Y$. Количество вхождений каждого значения складывается; например, сумма мультимножеств $\{1, 1, 2\}$ и $\{1, 2\}$ равна $\{1, 1, 1, 2, 2\}$.
• 3 X M K: Добавить в конец последовательности $f(a_X,M,K)$, где $f(S,M,K)$ получается путем удаления $K$ копий числа $M$ из $S$, если в $S$ есть хотя бы $K$ копий $M$, или добавления $K$ копий числа $M$ в $S$, если в $S$ строго меньше $K$ копий $M$.
• 4 X: Гарантируется, что $a_X$ состоит из единственного элемента. Выведите этот единственный элемент $a_X$.

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

Первая строка входных данных содержит единственное целое число $Q$ ($1 \le Q \le 5 \cdot 10^5$) — количество операций.

Следующие $Q$ строк содержат по одной операции каждая.

Гарантируется, что:

• Индексы $X$ и $Y$, используемые в операциях $2$, $3$ и $4$, всегда находятся в пределах текущей последовательности на момент выполнения операции.
• Значения $M$ и $K$, используемые в операциях $1$ и $3$, удовлетворяют условию $1 \le M,K \le 10^9$.
• Для всех операций типа $4$, $a_X$ содержит ровно один элемент.

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

Для каждой операции типа $4$ выведите строку с ответом.

Подзадачи

• ($10$ баллов) $1 \le M \le 10$ для всех операций типа $1$ и $3$.
• ($40$ баллов) Гарантируется, что в каждой операции типа $3$ новое мультимножество формируется путем удаления $K$ копий числа $M$ из $a_X$.
• ($50$ баллов) Без дополнительных ограничений.

Примеры

Пример 1

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

8
1 5 1
1 6 2
4 1
2 1 2
3 3 6 4
3 4 6 5
3 5 5 1
4 6

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

5
6

Примечание

Мультимножества выглядят следующим образом:

• $a_1 = \{5\}$.
• $a_2 = \{6, 6\}$.
• $a_3 = \{5, 6, 6\}$.
• $a_4 = \{5, 6, 6, 6, 6, 6, 6\}$.
• $a_5 = \{5, 6\}$.
• $a_6 = \{6\}$.