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 Codeforces
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int n=Integer.parseInt(bu.readLine());
        int N=500001,i,hm[]=new int[N],col[]=new int[n];
        ArrayList<Integer> g[]=new ArrayList[n],gr[]=new ArrayList[n];
        for(i=0;i<n;i++)
        {
            g[i]=new ArrayList<>();
            gr[i]=new ArrayList<>();
        }
        Arrays.fill(hm,-1);
        Arrays.fill(col,-1);

        boolean root[]=new boolean[n];
        for(i=0;i<n;i++)
        {
            String s[]=bu.readLine().split(" ");
            int t=Integer.parseInt(s[0]);
            if(t==1)
            {
                int x=Integer.parseInt(s[1]);
                if(hm[x]==-1)
                {
                    hm[x]=i;
                    root[hm[x]]=true;
                    col[i]=x;
                }
                g[hm[x]].add(i);    //add here
                continue;
            }

            int x=Integer.parseInt(s[1]),y=Integer.parseInt(s[2]);
            if(hm[x]==-1) continue;
            if(hm[y]==-1)
            {
                col[i]=y;
                hm[y]=i;
                root[i]=true;
            }

            gr[hm[y]].add(hm[x]);
            //System.out.println(hm[x]);
            root[hm[x]]=false;
            //System.out.println(root[hm[x]]);
            hm[x]=-1;
        }

        PriorityQueue<int[]> pq=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]>o2[0]) return 1;
                else return -1;
            }});

        boolean vis[]=new boolean[n];
        //for(i=0;i<n;i++) System.out.println(root[i]+" "+col[i]);
        //System.out.println();
        for(i=n-1;i>=0;i--)
        if(root[i]) dfs(gr,i,-1,col,col[i],vis);

        for(i=0;i<n;i++)
        for(int x:g[i]) pq.add(new int[]{x,col[i]});

        while(!pq.isEmpty()) sb.append(pq.poll()[1]+" ");
        System.out.print(sb);
    }

    static void dfs(ArrayList<Integer> g[],int n,int p,int col[],int c,boolean vis[])
    {
        col[n]=c;
        vis[n]=true;
        for(int x:g[n])
        if(x!=p) dfs(g,x,n,col,c,vis);
    }
}