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].
1
1 50
 1
1 114514
 1
1 2002
 1
1 500

50 
 114514 
 2002 
 500 

import java.io.*;
import java.util.*;

public class q4 {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    public static long mod = 1000000007;

    public static void solve() throws Exception {
        String[] parts = br.readLine().split(" ");
        int q = Integer.parseInt(parts[0]);

        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        int n = 0;
        for(int i = 0;i < q;i++){
            parts = br.readLine().split(" ");
            int id = Integer.parseInt(parts[0]);

            if(id == 1){
                int val = Integer.parseInt(parts[1]);

                ArrayList<Integer> arr = map.getOrDefault(val,new ArrayList<>());
                arr.add(n++);
                map.put(val,arr);
            }else{
                int x = Integer.parseInt(parts[1]);
                int y = Integer.parseInt(parts[2]);

                if(x == y) continue;
                ArrayList<Integer> a = map.getOrDefault(x,new ArrayList<>());
                ArrayList<Integer> b = map.getOrDefault(y,new ArrayList<>());

                map.remove(x);
                map.remove(y);

                if(a.size() < b.size()){
                    for(int val : a) b.add(val);
                    map.put(y,b);
                }else{
                    for(int val : b) a.add(val);
                    map.put(y,a);
                }
            }
        }

        int[] ans = new int[n];
        for(int val : map.keySet()){
            ArrayList<Integer> arr = map.get(val);
            for(int idx : arr) ans[idx] = val;
        }

        StringBuilder sb = new StringBuilder();
        for(int val : ans) sb.append(val).append(" ");
        System.out.println(sb);

    }

    public static void main(String[] args) throws Exception {
//        int tests = Integer.parseInt(br.readLine());
//        for (int test = 1; test <= tests; test++) {
            solve();
//        }
    }

//    public static ArrayList<Integer> primes;
//    public static void seive(int n){
//        primes = new ArrayList<>();
//        boolean[] arr = new boolean[n + 1];
//        Arrays.fill(arr,true);
//
//        for(int i = 2;i * i <= n;i++){
//            if(arr[i]) {
//                for (int j = i * i; j <= n; j += i) {
//                    arr[j] = false;
//                }
//            }
//        }
//        for(int i = 2;i <= n;i++) if(arr[i]) primes.add(i);
//    }
//    public static void sort(int[] arr){
//        ArrayList<Integer> temp = new ArrayList<>();
//        for(int val : arr) temp.add(val);
//
//        Collections.sort(temp);
//
//        for(int i = 0;i < arr.length;i++) arr[i] = temp.get(i);
//    }
//    public static void sort(long[] arr){
//        ArrayList<Long> temp = new ArrayList<>();
//        for(long val : arr) temp.add(val);
//
//        Collections.sort(temp);
//
//        for(int i = 0;i < arr.length;i++) arr[i] = temp.get(i);
//    }
//
//    public static long power(long a,long b,long mod){
//        if(b == 0) return 1;
//
//        long p = power(a,b / 2,mod);
//        p = (p * p) % mod;
//
//        if(b % 2 == 1) return (p * a) % mod;
//        return p;
//    }
//
//    public static int GCD(int a,int b){
//        return b == 0 ? a : GCD(b,a % b);
//    }
//    public static long GCD(long a,long b){
//        return b == 0 ? a : GCD(b,a % b);
//    }
//
//    public static int LCM(int a,int b){
//        return a * b / GCD(a,b);
//    }
//    public static long LCM(long a,long b){
//        return a * b / GCD(a,b);
//    }
}
