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.lang.*;
import java.io.*;
import java.awt.*;

/*AUTHOR - SHIVAM GUPTA */

// U KNOW THAT IF THIS DAY WILL BE URS THEN NO ONE CAN DEFEAT U HERE ,JUst keep faith in ur strengths .................................................. 
// ASCII = 48 + i ;// 2^28 = 268,435,456  > 2* 10^8 // log 10 base 2 = 3.3219 
// odd:: (x^2+1)/2 , (x^2-1)/2 ; x>=3// even:: (x^2/4)+1 ,(x^2/4)-1  x >=4 
// FOR ANY ODD NO N : N,N-1,N-2,ALL ARE PAIRWISE COPRIME,THEIR COMBINED LCM IS PRODUCT OF ALL THESE NOS
// two consecutive odds are always coprime to each other, two consecutive even have always gcd  = 2 ;

// Rectangle r = new Rectangle(int x , int y,int widht,int height) 
//Creates a rect. with bottom left cordinates as (x, y) and top right as ((x+width),(y+height))

//BY DEFAULT Priority Queue is MIN in nature in java
//to use as max , just push with negative sign and change sign after removal 

// We can make a sieve of max size 1e7 .(no time or space issue) 
// In 1e7 starting nos we have about 66*1e4 prime nos
// In 1e6 starting nos we have about 78,498 prime nos

 public class Main
 //public class Solution
{
    static PrintWriter out;
    
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		public FastReader(){
			br=new BufferedReader(new InputStreamReader(System.in));
			out=new PrintWriter(System.out);
		}
		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;
		}
	}
	
///////////////////////////////////////////////////////////


static LLnode[] h ;
static LLnode[] t ;
static int id ;

static void add(int x)
{
     LLnode newnode =new LLnode(id) ;
    
    if(t[x] == null){
        
        h[x] =newnode ;
        t[x] =newnode ;
    }
    
    else{
        
        t[x].next =newnode ;
        t[x]=newnode;
        
    }
}


static void move(int x, int y)
{
    if(x==y)return ;
    
    if(h[x] ==null)return ;
    
    
    if(t[y] == null)
    {
        h[y]=h[x] ;
        t[y]=t[x] ;
    }
    
    else{
        t[y].next=h[x] ;
        t[y] =t[x] ;
        
       
    }
    
     h[x]=null;
     t[x]=null;
    
}

public static void solve()
{
FastReader scn = new FastReader() ;


int q= scn.nextInt() ;

int size = 500001 ;

id= 0 ;

 h = new LLnode[size] ;
 t = new LLnode[size] ;





while(q-- > 0)
{
    int type =scn.nextInt() ;
    
    
    if(type == 1)
    {
        int x = scn.nextInt() ;
        
        add(x) ;
        
        id++ ;
    }
    
    
    else{
        
        
         int x = scn.nextInt() ; int y = scn.nextInt() ;
         
         move(x,y) ;
        
    }
    
}

 int[] ans  = new int[id] ;
 
 for(int i =1; i<= 500000;i++)
{

    LLnode temp =h[i] ;
    
    while(temp != null)
    {
        ans[temp.data]=i ;temp =temp.next ;
    }
    
}


for(int x:  ans) out.print(x+" ");

out.println() ;





out.flush() ;  
} // solve fn ends


public static void main (String[] args) throws java.lang.Exception
{     solve() ;    }
      
}
  
class LLnode{
    
    int data;
    LLnode next ;
    
    public LLnode(int data)
    {
        this.data =data ;
        this.next =null ;
    }
    
    
    
}