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 E {
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
			System.setOut(new PrintStream(new FileOutputStream("output.txt")));
		} catch (Exception e) {
			System.err.println(e.toString());
		}
		Scanner sc = new Scanner(System.in);
		int tc = 1;
		for(int ti = 1; ti <= tc; ti++) {
			int len = sc.nextInt();
			DJS djs = new DJS(len);
			for(int i = 0; i < len; i++) {
				int kk = sc.nextInt();
				if(kk == 1) {
					int x = sc.nextInt();
					djs.add(x);
				} else {
					int x = sc.nextInt();
					int y = sc.nextInt();
					djs.change(x, y);
				}
			}
			System.out.println(djs.getResult());
		}
	}

	static class DJS {
		int[] par;
		int[] rank;
		int st = 0;
		int[] val;
		List<Integer> list = new ArrayList<>();
		public DJS(int len) {
			par = new int[len+1];
			for(int i = 0; i <= len; i++)
				par[i] = i;
			val = new int[500005];
			rank = new int[len+1];
			list.add(0);
		}

		public int find(int ind) {
			if(par[ind] == ind)
				return ind;
			int pp = find(par[ind]);
			par[ind] = pp;
			return pp;
		}

		public int union(int ind1, int ind2) {
			int par1 = find(ind1);
			int par2 = find(ind2);
			if(par1 == par2)
				return par1;
			if(rank[par1] >= rank[par2]) {
				rank[par1]++;
				par[par2] = par1;
				return par1;
			} else {
				rank[par2]++;
				par[par1] = par2;
				return par2;
			}
		}


		public void add(int vv) {
			st++;
			list.add(vv);
			if(val[vv] == 0) {
				val[vv] = st;
			} else {
				union(val[vv], st);
			}
		}

		public void change(int x, int y) {
			if(val[x] == 0)
				return;
			if(val[y] == 0) {
				val[y] = val[x];
				list.set(val[x], y);
			} else {
				int pp = union(val[y], val[x]);
				list.set(pp, y);
			}
			val[x] = 0;
		}

		public String getResult() {
			StringBuilder sb = new StringBuilder();
			for(int i = 1; i <= st; i++) {
				int pp = find(i);
				sb.append(list.get(pp)+ " ");
			}
			return sb.toString();
		}
	}
}