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.util.*;
import java.io.*;
public class Main {
		static long mod = 1000000007;
		static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		public static void main(String[] args) throws IOException  {
			FastReader sc = new FastReader();
			ArrayList<Integer> arr[] = new ArrayList[(int)5e5+1];
			int n = (int)5e5 ;
			for( int i = 1 ;i <= n ;i++) {
				arr[i] = new ArrayList<>();
			}
			int q = sc.nextInt();
			int i = 0;
			while( q-- > 0) {
				int temp = sc.nextInt();
				if( temp == 1) {
					int input = sc.nextInt();
					arr[input].add(i);
					i++;
				}
				else {
					int fst = sc.nextInt();
					int scnd = sc.nextInt();
					int sf = arr[fst].size();
					int ss = arr[scnd].size();
					if( fst!= scnd) {
					if(  sf > ss) {
						ArrayList<Integer> tem = new ArrayList<>();
						tem = arr[fst];
						arr[fst] = arr[scnd];
						arr[scnd] = tem;
					}
					arr[scnd].addAll(arr[fst]);
					arr[fst].clear();
					
//					out.println(arr[fst]);
//					out.println(arr[scnd]);
					}
				}
			}
			int a[] = new int [n];
			for(  i = 1 ; i<= n ; i++) {
				int size = arr[i].size();
				if( size != 0) {
					for( int j = 0 ; j< size ; j++) {
						a[arr[i].get(j)] = i;
					}
				}
			}
			for( i = 0 ;i< n ;i++) {
				if( a[i] != 0) {
					out.print(a[i] + " ");
				}
			}
			out.println();
			out.flush();
		}
		/*
		 * WARNING -> DONT EVER USE ARRAYS.SORT() IN ANY WAY.
		 * FIRST AND VERY IMP -> READ AND UNDERSTAND THE QUESTION VERY CAREFULLY.
		 * WARNING -> DONT CODE BULLSHIT , ALWAYS CHECK THE LOGIC ON MULTIPLE TESTCASES AND EDGECASES BEFORE. 
		 * SECOND -> TRY TO FIND RELEVENT PATTERN SMARTLY.
		 * WARNING -> IF YOU THINK YOUR SOLUION IS JUST DUMB DONT SUBMIT IT BEFORE RECHECKING ON YOUR END.
		 */
		public static boolean ifpowof2(long n ) {
			return ((n&(n-1)) == 0);
		}
		
		static boolean isprime(long x ) {
			if( x== 2) {
				return true;
			}
			if( x%2 == 0) {
				return false;
			}
			for( long i = 3 ;i*i <= x ;i+=2) {
				if( x%i == 0) {
					return false;
				}	
			}
			return true;
		}
		
		static boolean[] sieveOfEratosthenes(long n) { 
			boolean prime[] = new boolean[(int)n + 1];
			for (int i = 0; i <= n; i++) {
				prime[i] = true;
			}
			for (long p = 2; p * p <= n; p++) {   
				if (prime[(int)p] == true) {
					for (long i = p * p; i <= n; i += p)
						prime[(int)i] = false;
				}
			}		 
			return prime;
		}
		
		public static int[] nextLargerElement(int[] arr, int n)	{ 
			Stack<Integer> stack = new Stack<>();
			int rtrn[] = new int[n];
			rtrn[n-1] = -1;
	        stack.push( n-1);
	        for( int i = n-2 ;i >= 0 ; i--){
	            int temp = arr[i];
	            int lol = -1;
	            while( !stack.isEmpty() && arr[stack.peek()] <= temp){
	            	if(arr[stack.peek()] == temp ) {
	            		lol = stack.peek();
	            	}
	                stack.pop();
	            }
	            if( stack.isEmpty()){
	            	if( lol != -1) {
	            		rtrn[i] = lol;
	            	}
	            	else {
	            		rtrn[i] = -1;
	            	}
	            }
	            else{
	            	rtrn[i] = stack.peek();
	            }
	            stack.push( i);
	        }
	        return rtrn;
		}
		
		static void mysort(int[] arr) {
			for(int i=0;i<arr.length;i++) {
	            int rand = (int) (Math.random() * arr.length);
	            int loc = arr[rand];
	            arr[rand] = arr[i];
	            arr[i] = loc;
	        }
	        Arrays.sort(arr);
	    }
		
		
		static void mySort(long[] arr) {
	        for(int i=0;i<arr.length;i++) {
	            int rand = (int) (Math.random() * arr.length);
	            long loc = arr[rand];
	            arr[rand] = arr[i];
	            arr[i] = loc;
	        }
	        Arrays.sort(arr);
	    }
		
		static long gcd(long a, long b)
		{
			if (a == 0)
				return b;
			return gcd(b % a, a);
		}
		
			   
		 static long lcm(long a, long b)
		 {
			 return (a / gcd(a, b)) * b;
		 }
		 

		 static long rightmostsetbit(long n) {
			 return n&-n;
		 }
		 
		 static long leftmostsetbit(long n)
		    {
		        long k = (long)(Math.log(n) / Math.log(2));
		        return 1 << k;
		    }
	 
		 static HashMap<Long,Long> primefactor( long n){
			 HashMap<Long ,Long> hm = new HashMap<>();
			 long temp = 0;
			 while( n%2 == 0) {
				 temp++;
				 n/=2;
			 }	
			 if( temp!= 0) {
				 hm.put( 2L, temp);
			 }
			 long c = (long)Math.sqrt(n);
			 for( long i = 3 ; i <= c ; i+=2) {
				 temp = 0;
				 while( n% i == 0) {
					 temp++;
					 n/=i;
				 }
				 if( temp!= 0) {
					 hm.put( i, temp);
				 }
	 		 }
	 		 if( n!= 1) {
	 			 hm.put( n , 1L);
	 		 }
	 		 return hm;	
		 }
		 
		 
		 static ArrayList<Integer> allfactors(int abs) {
			 HashMap<Integer,Integer> hm = new HashMap<>();
			 ArrayList<Integer> rtrn = new ArrayList<>();
			 for( int i = 2 ;i*i <= abs; i++) {
				 if( abs% i == 0) {
					 hm.put( i , 0);
					 hm.put(abs/i, 0);
				 }
			 }
			 for( int x : hm.keySet()) {
				 rtrn.add(x);
			 }
			 
			 if( abs != 0) {
				 rtrn.add(abs);
			 }
			 
			 return rtrn;
		 }
			
	 
		 static class FastReader {
			 BufferedReader br;
			 StringTokenizer st;
		 
			 public FastReader()
			 {
				 br = new BufferedReader(new InputStreamReader(System.in));
			 }
		        
			 String next()
			 {
				 while (st == null || !st.hasMoreElements()) {
					 try {
						 st = new StringTokenizer(br.readLine());
					 }
					 catch (IOException e) {
						 e.printStackTrace();
					 }
				 }
				 return st.nextToken();
			 }
		 
			 int nextInt() { return Integer.parseInt(next()); }
			 
			 long nextLong() { return Long.parseLong(next()); }
			 
			 double nextDouble()
			 {
				 return Double.parseDouble(next());
			 }	
		 
			 String nextLine()
			 {
				 String str = "";
				 try {
					 str = br.readLine();
				 }
				 catch (IOException e) {
					 e.printStackTrace();
				 }
				 return str;
			 }
		 }	
}

 