human
Write me a Python program to find the resulting array after performing all the queries given the following:
You have an array of integers (initially empty).

You have to perform q queries. Each query is of one of two types: 

  * "1 x" — add the element x to the end of the array.

  * "2 x y" — replace all occurrences of x in the array with y. 


Find the resulting array after performing all the queries.

Input

The first line contains a single integer q (1 ≤ q ≤ 5 ⋅ 10^5) — the number of queries.

Next q lines contain queries (one per line). Each query is of one of two types: 

  * "1 x" (1 ≤ x ≤ 5 ⋅ 10^5).

  * "2 x y" (1 ≤ x, y ≤ 5 ⋅ 10^5). 


It's guaranteed that there is at least one query of the first type.

Output

In a single line, print k integers — the resulting array after performing all the queries, where k is the number of queries of the first type.

Examples

Input

7
1 3
1 1
2 1 2
1 2
1 1
1 2
2 1 3

Output

3 2 2 3 2 

Input

4
1 1
1 2
1 1
2 2 2

Output

1 2 1 

Input

8
2 1 4
1 1
1 4
1 2
2 2 4
2 4 3
1 2
2 2 7

Output

1 3 3 7 

Note

In the first example, the array changes as follows:

[] → [3] → [3, 1] → [3, 2] → [3, 2, 2] → [3, 2, 2, 1] → [3, 2, 2, 1, 2] → [3, 2, 2, 3, 2].

In the second example, the array changes as follows:

[] → [1] → [1, 2] → [1, 2, 1] → [1, 2, 1].

In the third example, the array changes as follows:

[] → [] → [1] → [1, 4] → [1, 4, 2] → [1, 4, 4] → [1, 3, 3] → [1, 3, 3, 2] → [1, 3, 3, 7].
assistant
#Here is Python program to find the resulting array after performing all the queries.

# cook your dish here
import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_=lambda: sys.stdin.readline().strip("\r\n")
from math import log
from math import gcd
from math import atan2,acos
from random import randint
sa=lambda :input_()
sb=lambda:int(input_())
sc=lambda:input_().split()
sd=lambda:list(map(int,input_().split()))
sflo=lambda:list(map(float,input_().split()))
se=lambda:float(input_())
sf=lambda:list(input_())
flsh=lambda: sys.stdout.flush()
sys.setrecursionlimit(3*10**5)
mod=10**9+7
mod1=998244353
gp=[]
cost=[]
dp=[]
mx=[]
ans1=[]
ans2=[]
special=[]
specnode=[]
a=0
kthpar=[]
def dfs2(root,par):
    if par!=-1:
        dp[root]=dp[par]+1
    for i in range(1,20):
        if kthpar[root][i-1]!=-1:
            kthpar[root][i]=kthpar[kthpar[root][i-1]][i-1]
    for child in gp[root]:
        if child==par:continue
        kthpar[child][0]=root
        dfs(child,root)
        
ans=0
a=[]
n,k=0,0
b=[]
vis=[]
tot=0
time=[]
time1=[]
adj=[]
mx=-1
eps=0.0000001
x=0
pref=[]
lvl=[]
gp=[]
ans=[]
f=0
w=[]

def dfs(i,prod,rem,n):
    if rem==0:
        while(i<len(n)):
            prod*=int(n[i])
            i+=1
        return prod
    if i==len(n):
        return prod
    mx=0
    for j in range(9-int(n[i])):
        mx=max(dfs(i+1,(int(n[i])+min(j,rem))*prod,rem-min(j,rem),n),mx)
    return mx
class Disjoint_SU:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.size=[1 for i in range(n)]
    #find
    def lake_de(self,a):
        if a==self.parent[a]:
            return a
        self.parent[a]=self.lake_de(self.parent[a])
        return self.parent[a]
    #union
    #by size
    def jod(self,a,b):
        x=self.lake_de(a)
        y=self.lake_de(b)
        #for cycle in graph
        if x==y:
            return True
        if self.size[x]>self.size[y]:
            self.size[x]+=self.size[y]
            self.parent[y]=x
        else:
            self.size[y]+=self.size[x]
            self.parent[x]=y
        return False
def...