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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.StringTokenizer;

public class A5 {

    void solve() {
        TIntList[] map = new TIntList[500_001];
        int n = cint();
        int index = 0;
        for (int i = 0; i < n; i++) {
            String line = cstr();
            if (line.startsWith("1")) {
                int x = Integer.parseInt(line.substring(2));
                TIntList list = map[x];
                if (list == null) {
                    map[x] = list = new TIntList();
                }
                list.add(index);
                index++;
            } else {
                String[] p = line.substring(2).split("[\\s]");
                int x = Integer.parseInt(p[0]);
                int y = Integer.parseInt(p[1]);
                TIntList list = map[x];
                if (list != null) {
                    map[x] = null;
                    TIntList list2 = map[y];
                    if (list2 != null) {
                        list2.add(list);
                    } else {
                        map[y] = list;
                    }
                }
            }
        }
        
        int[] a = new int[index];
        ArrayDeque<TIntList> queue = new ArrayDeque<>();
        for (int x = 1; x < map.length; x++) {
            TIntList list = map[x];
            if (list != null) {
                queue.add(list);
                list.value = x;
            }
        }
        
        while (!queue.isEmpty()) {
            TIntList list = queue.removeFirst();
            int x = list.value;
            for (int i = 0; i < list.len; i++) {
                a[list.x[i]] = x;
            }
            for (int i = 0; i < list.leny; i++) {
                list.y[i].value = x;
                queue.addLast(list.y[i]);
            }
        }
        
        cout(a);
    }

    
    
    class TIntList {
        int[] x;
        TIntList[] y;
        int len;
        int leny;
        
        int value;

        public TIntList() {
            this.x = new int[3];
            this.y = new TIntList[3];
        }
        public void add(int val) {
            if (len >= x.length) {
                x = Arrays.copyOf(x, 3 * x.length / 2 + 1);
            }
            x[len++] = val;
        }
        public void add(TIntList val) {
            if (leny >= y.length) {
                y = Arrays.copyOf(y, 3 * y.length / 2 + 1);
            }
            y[leny++] = val;
        }
    }

    
    public static void main(String... args) {
//        int t = in.nextInt();
//        for (int test = 0; test < t; test++) {
            new A5().solve();
//        }
        out.flush();
    }

    static final QuickReader in = new QuickReader(System.in);
    static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out, 131_072));

    static int cint() {
        return in.nextInt();
    }

    static long clong() {
        return in.nextLong();
    }

    static String cstr() {
        return in.nextLine();
    }

    static int[] carr_int(int n) {
        return in.nextInts(n);
    }

    static long[] carr_long(int n) {
        return in.nextLongs(n);
    }

    static void cout(int... a) {
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                buf.append(' ');
            }
            buf.append(a[i]);
        }
        out.println(buf);
    }

    static void cout(long... a) {
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                buf.append(' ');
            }
            buf.append(a[i]);
        }
        out.println(buf);
    }

    static void cout(Object o) {
        out.println(o);
    }

    static class QuickReader {
        BufferedReader in;
        StringTokenizer token;

        public QuickReader(InputStream ins) {
            in = new BufferedReader(new InputStreamReader(ins), 100_000);
            token = new StringTokenizer("");
        }

        public boolean hasNext() {
            while (!token.hasMoreTokens()) {
                try {
                    String s = in.readLine();
                    if (s == null) {
                        return false;
                    }
                    token = new StringTokenizer(s);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return true;
        }

        public String next() {
            hasNext();
            return token.nextToken();
        }

        public String nextLine() {
            try {
                String s = in.readLine();
                token = new StringTokenizer("");
                return s;
            } catch (IOException e) {
                throw new InputMismatchException();
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public int[] nextInts(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt();
            }
            return res;
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public long[] nextLongs(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong();
            }
            return res;
        }
    }
}
