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 com.sun.source.util.DocTreePathScanner;

import java.io.*;
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static class Config {
        public static Boolean multiCase = false;
        public static Boolean debug = false; // 这里设为true不一定有效，还需要把进程的参数设为 local
    }


    public static IOUtils.FastScanner scanner = new IOUtils.FastScanner(new BufferedInputStream(System.in, 1 << 20)); // 1MB buffer
    public static PrintStream printStream = new PrintStream(new BufferedOutputStream(System.out, 1 << 20)); // 1MB buffer
    public static Random random = new Random();

    public static void simpleCase(int caseNumber) {
        List<List<Integer>> queryList = new ArrayList<>();
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            queryList.add(IOUtils.readIntList());
        }

        DataStructs.IntArrayList ans = new DataStructs.IntArrayList();
        DataStructs.IntArrayMap replace = new DataStructs.IntArrayMap(0, (int) 5e5, -1);
        for (int i = n - 1; i >= 0; i--) {
            List<Integer> op = queryList.get(i);
            if (op.size() == 1) {
                ans.add(replace.getOrDefault(op.get(0), op.get(0)));
            } else {
                if (replace.containsKey(op.get(1))) {
                    replace.put(op.get(0), replace.get(op.get(1)));
                } else {
                    replace.put(op.get(0), op.get(1));
                }
            }
        }
        IOUtils.printRevertIntList(ans.size(), ans);
    }

    public static void main(String[] args) throws IOException {
        Config.debug = Config.debug && args.length == 1 && args[0].equals("local");
        if (Config.debug) {
            printStream = System.out;
            Algorithm.Test.test();
        }
        if (Config.multiCase) {
            IntStream.range(1, 1 + scanner.nextInt()).forEach(Main::simpleCase);
        } else {
            simpleCase(1);
        }
        printStream.flush();
        System.in.close();
        System.out.close();
    }

    public static class Algorithm {
        /**
         * 寻找第一个满足check的数据<br/>
         * 要求： 如果i满足，则i+1一定满足<br/>
         * 可视化情况：????????????????????????????????<br/>
         * &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;
         * &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;↑
         *
         * @param ql    左端点 include
         * @param qr    右端点 exclude
         * @param check 检验函数
         * @return 二分的值
         */
        public static long searchTheFirstOne(long ql, long qr, Function<Long, Boolean> check) {
            long l = ql, r = qr - 1;
            while (l < r) {
                long mid = (l + r) >> 1;
                if (check.apply(mid)) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (Config.debug) {
                Assert.isTrue(ql < qr, "二分区间不存在");
                Assert.isTrue(l <= ql || random.longs(100, ql, l).noneMatch(check::apply), "二分的check函数不满足ans的前缀均为false");
                Assert.isTrue(qr <= l || random.longs(100, l, qr).allMatch(check::apply), "二分的check函数不满足ans的后缀均为true");
            }
            return l;
        }

        /**
         * 寻找最后一个满足check的数据<br/>
         * 要求： 如果i满足，则i-1一定满足<br/>
         * 可视化情况：????????????????????????????????<br/>
         * &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;
         * &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;↑
         *
         * @param ql    左端点 include
         * @param qr    右端点 exclude
         * @param check 检验函数
         * @return 二分的值
         */
        public static long searchTheLastOne(long ql, long qr, Function<Long, Boolean> check) {
            long l = ql, r = qr - 1;
            while (l < r) {
                long mid = (l + r + 1) >> 1;
                if (check.apply(mid)) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            if (Config.debug) {
                Assert.isTrue(ql < qr, "二分区间不存在");
                Assert.isTrue(random.longs(100, ql, l + 1).allMatch(check::apply), "二分的check函数不满足ans的前缀均为true");
                Assert.isTrue(random.longs(100, l + 1, qr).noneMatch(check::apply), "二分的check函数不满足ans的后缀均为false");
            }
            return l;
        }

        public static class Test {
            public static void searchTheFirstOneTest() {
                int[] list = {2, 3, 5, 7, 11, 13, 17, 19, 21, 29, 31, 37};
                // 寻找第一个大于x的数
                int[][] listq = {
                        {1, 2}, {2, 3}, {3, 5}, {4, 5},
                        {5, 7}, {6, 7}, {7, 11}, {12, 13},
                        {20, 21}, {21, 29}, {31, 37}, {36, 37},
                };
                Arrays.stream(listq).forEach(q -> {
                    int index = (int) searchTheFirstOne(0, list.length, i -> list[i.intValue()] > q[0]);
                    Assert.isTrue(list[index] == q[1], "测试失败");
                });
            }

            public static void searchTheLastOneTest() {
                int[] list = {2, 3, 5, 7, 11, 13, 17, 19, 21, 29, 31, 37};
                // 寻找第一个小于x的数
                int[][] qs = {
                        {3, 2}, {4, 3}, {5, 3}, {6, 5},
                        {9, 7}, {10, 7}, {11, 7}, {12, 11},
                        {20, 19}, {21, 19}, {31, 29}, {36, 31},
                };
                Arrays.stream(qs).forEach(q -> {
                    int index = (int) searchTheLastOne(0, list.length, i -> list[i.intValue()] < q[0]);
                    Assert.isTrue(list[index] == q[1], "测试失败");
                });
            }

            public static void test() {
                searchTheFirstOneTest();
                searchTheLastOneTest();
                printStream.println("Algorithm类： 测试成功");
            }
        }

    }


    public static class IOUtils {
        public static List<Integer> readIntList() {
            int size = scanner.nextInt();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                list.add(scanner.nextInt());
            }
            return list;
        }

        public static List<Integer> readIntList(int size) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                list.add(scanner.nextInt());
            }
            return list;
        }

        public static void printIntList(int size, List<Integer> list) {
            if (Config.debug) {
                Assert.isTrue(list.size() <= size, "list 输出错误");
            }
            for (int i = 0; i < size; i++) {
                printStream.print(list.get(i));
                printStream.print(i == size - 1 ? '\n' : ' ');
            }
        }

        public static void printRevertIntList(int size, List<Integer> list) {
            if (Config.debug) {
                Assert.isTrue(list.size() <= size, "list 输出错误");
            }
            for (int i = size - 1; i >= 0; i--) {
                printStream.print(list.get(i));
                printStream.print(i == 0 ? '\n' : ' ');
            }
        }

        public static void printRevertIntList(int size, DataStructs.IntArrayList list) {
            if (Config.debug) {
                Assert.isTrue(list.size() <= size, "list 输出错误");
            }
            for (int i = size - 1; i >= 0; i--) {
                printStream.print(list.get(i));
                printStream.print(i == 0 ? '\n' : ' ');
            }
        }

        public static void printList(List<Integer> list, String sizeSplit) {
            printStream.print(list.size());
            printStream.print(sizeSplit);
            String collect = list.stream().map(Object::toString).collect(Collectors.joining(" "));
            printStream.println(collect);
        }

        public static class FastScanner {
            BufferedReader br;
            StringTokenizer st;

            public FastScanner(InputStream source) {
                br = new BufferedReader(new InputStreamReader(source));
            }

            String next() {
                while (st == null || !st.hasMoreElements()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return st.nextToken();
            }

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

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

            public double nextDouble() {
                return Double.parseDouble(next());
            }

            public String nextLine() {
                String str = "";
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                return str;
            }
        }
    }

    public static class Assert {
        public static void isTrue(Boolean check, String msg) {
            if (!check) {
                throw new RuntimeException("error: " + msg);
            }
        }
    }

    public static class DataStructs {
        public static final class ArrayMap<V> implements Map<Integer, V> {
            int minValue;
            int maxValue;
            int size;
            Object[] array;

            ArrayMap(int minValue, int maxValue) {
                if (Config.debug) {
                    Assert.isTrue(minValue == 0, "");
                }
                this.minValue = minValue;
                this.maxValue = maxValue;
                this.size = 0;
                this.array = new Object[this.maxValue - this.minValue + 1];
            }

            @Override
            public int size() {
                return size;
            }

            @Override
            public boolean isEmpty() {
                return size == 0;
            }

            @Override
            public boolean containsKey(Object key) {
                if (Config.debug) {
                    Assert.isTrue(key instanceof Integer, "key 类型不对");
                }
                return array[(int) key] != null;
            }

            @Override
            public boolean containsValue(Object value) {
                if (Config.debug) {
                    throw new RuntimeException("未实现的方法");
                }
                return false;
            }

            @Override
            public V get(Object key) {
                if (Config.debug) {
                    Assert.isTrue(key instanceof Integer, "key 类型不对");
                }
                return (V) array[(int) key];
            }

            @Override
            public V put(Integer key, V value) {
                Object old = array[(int) key];
                array[(int) key] = value;
                return (V) old;
            }

            @Override
            public V remove(Object key) {
                if (Config.debug) {
                    Assert.isTrue(key instanceof Integer, "key 类型不对");
                }
                Object old = array[(int) key];
                array[(int) key] = null;
                return (V) old;
            }

            @Override
            public void putAll(Map<? extends Integer, ? extends V> m) {
                if (Config.debug) {
                    throw new RuntimeException("未实现的方法");
                }
            }

            @Override
            public void clear() {
                size = 0;
                this.array = new Object[this.maxValue - this.minValue + 1];
            }

            @Override
            public Set<Integer> keySet() {
                if (Config.debug) {
                    throw new RuntimeException("未实现的方法");
                }
                return null;
            }

            @Override
            public Collection<V> values() {
                if (Config.debug) {
                    throw new RuntimeException("未实现的方法");
                }
                return null;
            }

            @Override
            public Set<Entry<Integer, V>> entrySet() {
                if (Config.debug) {
                    throw new RuntimeException("未实现的方法");
                }
                return null;
            }
        }

        public static final class IntArrayMap {
            int minValue;
            int maxValue;
            int notUseTag;
            int size;
            int[] array;

            public IntArrayMap(int minValue, int maxValue, int notUseTag) {
                this.minValue = minValue;
                this.maxValue = maxValue;
                this.notUseTag = notUseTag;
                this.size = 0;
                this.array = new int[this.maxValue - this.minValue + 1];
                Arrays.fill(array, notUseTag);
            }


            public int getOrDefault(int key, int defaultValue) {
                return array[key] == notUseTag ? defaultValue : array[key];
            }

            public boolean containsKey(int key) {
                return array[key] != notUseTag;
            }

            public int get(int key) {
                return array[key];
            }

            public void put(int key, int value) {
                array[key] = value;
            }
        }

        public static final class IntArrayList {

            int size;
            int[] values;

            IntArrayList() {
                size = 0;
                values = new int[2];
            }

            public void add(Integer value) {
                if (size == values.length) {
                    int[] old = values;
                    values = new int[2 * size];
                    System.arraycopy(old, 0, values, 0, size);
                }
                values[size++] = value;
            }

            public int size() {
                return size;
            }

            public int get(int i) {
                return values[i];
            }
        }
    }
}