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 Main {
	
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		byte[] bb = new byte[1 << 15]; int i, n;
		byte getc() {
			if (i == n) {
				i = n = 0;
				try { n = in.read(bb); } catch (IOException e) {}
			}
			return i < n ? bb[i++] : 0;
		}
		int nextInt() {
			byte c = 0; while (c <= ' ') c = getc();
			int a = 0; while (c > ' ') { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	
	static class Node {
		int origIdx;
		Node next;
		Node(int origIdx) {
			this.origIdx = origIdx;
			this.next = null;
		}
	}
	
	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));		
		
		Node[] first = new Node[500500];
		Node[] last = new Node[500500];
		int index = 0;
		int Q = in.nextInt();
		
		for (int ts=1; ts<=Q; ts++) {
			int type = in.nextInt();
			if (type == 1) {
				int value = in.nextInt();
				index++;
				Node node = new Node(index);
				if (first[value] == null) {
					first[value] = node;
					last[value] = node;
				} else {
					last[value].next = node;
					last[value] = node;
				}
			} else {
				int x = in.nextInt();
				int y = in.nextInt();
				
				if (x == y) continue;
				if (first[x] != null) {
					last[x].next = first[y];
					
					first[y] = first[x];
					
					if (last[y] == null) {
						last[y] = last[x];
					}
					
					first[x] = last[x] = null;
				}
			}
			
			/*System.out.println("******START");
			for (int i=1; i<=500000; i++) {
				if (first[i] == null) continue;
				
				
				System.out.println(i);
				Node node = first[i];
				while (node != null) {
					System.out.print(node.origIdx + " ");
					node = node.next;
				}
				System.out.println();
				System.out.println("first " + first[i]);
				System.out.println("last " + last[i]);
			}
			System.out.println("******END");*/
		}
		
		
		int[] result = new int[500050];
		for (int i=1; i<=500000; i++) {
			if (first[i] == null) continue;
			
			
			//System.out.println(i);
			Node node = first[i];
			while (node != null) {
				//System.out.print(node.origIdx + " ");
				result[node.origIdx] = i;
				node = node.next;
			}
			//System.out.println();
		}
		
		out.write(result[1] + "");
		for (int i=2; i<=index; i++) {
			out.write(" " + result[i]);
		}
		out.write("\n");
		
		out.close();
	}

}
