Problem C
Equivalent Exchange

It is impossible to create something out of nothing. In order to obtain something, something of equal value must be given.

Two brothers, who seek to increase their understanding of alchemy, were left stranded on a deserted island by their mentor. With no other way to survive, they try to use their abilities to gather resources.

They’ve documented their stay over $d$ days, tracking how many of each item they have. They’ve given each item an integer ID, ranging from $1$ to $10^9$. On the $i$th day, one of two things happen:

1. The younger brother finds one of item $f_ i$.

2. The older brother transmutes all their stock of item $s_ i$ to item $d_ i$.

As they depart the island, they wish to look back on what they’ve learned so far. To do so, they take inventory of the items they’ve gathered one last time. Can you do the same?

Input

The first line of input contains one integer $1 \leq d \leq 5 \cdot 10^5$, the number of days. The next $d$ lines each contain a query. Each of these lines contains a series of space-separated integers. The first integer is $t_ i \in \{ 1, 2\} $, the type of query.

• If $t_ i = 1$, the next integer is $f_ i$. It is guaranteed that there exists at least one query of this type.

• If $t_ i = 2$, the next two integers are $s_ i$ and $d_ i$.

Output

Let the days where some item was found be $x_1, x_2, \dots , x_ n$. Print $n$ lines. On the $i$th line, print the final item ID of the item found on day $x_ i$.

8
1 10
1 5
1 7
2 10 9
1 7
1 10
2 7 8
1 3

9
5
8
8
10
3