Busy Beaver likes data structure problems, but he thinks that data structure problems on arrays with interval queries are boring. So he came up with a different kind of data structure problem, with multisets!

There is a sequence $a_1, \dots, a_L$, where each $a_i$ is a multiset of positive integers. Initially, the sequence is empty, i.e. $L=0$. Implement the following operations:

• 1 M K: Add a multiset consisting of only the number $M$ appearing $K$ times to the end of the sequence.
• 2 X Y: Add the sum of $a_X$ and $a_Y$ to the end of the sequence. The number of occurrences of each value adds; for example, we define the sum of multisets $\{1, 1, 2\}$ and $\{1, 2\}$ to be $\{1, 1, 1, 2, 2\}$.
• 3 X M K: Add $f(a_X,M,K)$ to the end of the sequence, where $f(S,M,K)$ is formed by removing $K$ copies of $M$ from $S$ if $S$ has at least $K$ copies of $M$, or adding $K$ copies of $M$ to $S$ if $S$ has strictly fewer than $K$ copies of $M$.
• 4 X: It is guaranteed that $a_X$ consists of a single element. Output this single element of $a_X$.

Input

The first line of input contains a single integer $Q$ ($1 \le Q \le 5 \cdot 10^5$), the number of operations.

The next $Q$ lines contain one operation each.

It is guaranteed that:

• The indices $X$ and $Y$ used in operations $2$, $3$, and $4$ always remain within the sequence at the time of the operation.
• The values $M$ and $K$ used in operation $1$ and $3$ satisfy $1 \le M,K \le 10^9$.
• For all type $4$ operations, $a_X$ contains exactly one element.

Output

For each type $4$ operation, output a line with the answer.

Scoring

• ($10$ points) $1 \le M \le 10$ for all type $1$ and $3$ operations.
• ($40$ points) It is guaranteed that in each type $3$ operation, the newly appended multiset is formed by removing $K$ copies of $M$ from $a_X$.
• ($50$ points) No additional constraints.

Examples

Input 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

Output 1

5
6

Note

The multisets are as follows:

• $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\}$.