human
Can you provide a Python code 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 code to find the resulting array after performing all the queries.

def main():
    
    q = int(input())
    indexes = [[] for __ in range(500005)] # store {value:[indexes]}
    i = 0
    for _ in range(q):
        zz = readIntArr()
        if zz[0] == 1:
            indexes[zz[1]].append(i)
            i += 1
        else:
            x = zz[1]
            y = zz[2]
            if x == y or len(indexes[x]) == 0:
                continue
            if len(indexes[x]) < len(indexes[y]):
                arr1 = indexes[x]
                arr2 = indexes[y]
            else:
                arr1 = indexes[y]
                arr2 = indexes[x]
            # arr1 is smaller
            for z in arr1:
                arr2.append(z)
            indexes[x] = []
            indexes[y] = arr2
    ans = [-1] * i
    for k, v in enumerate(indexes):
        for i in v:
            ans[i] = k
    oneLineArrayPrint(ans)
    
    return

import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
# input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ansArr):
    print('! {}'.format(' '.join([str(x) for x in ansArr])))
    sys.stdout.flush()
 
inf=float('inf')
# MOD=10**9+7
# MOD=998244353

from math import gcd,floor,ceil
import math
# from math import floor,ceil # for...