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 Solution{
	static int[] p, rank, setSize, col;
	static int numSets,N;
	static void preDSU(int n) {
		N=n;
		p = new int[numSets = N];
		rank = new int[N];
		setSize = new int[N];
		col=new int[N];
	}
	static void addNode(int idx,int c){
		p[idx]=idx;
		setSize[idx]=1;
		col[idx]=c;
	}
	static int findSet(int i) { return p[i] == i ? i : (p[i] = findSet(p[i])); }

	static boolean isSameSet(int i, int j) { return findSet(i) == findSet(j); }

	static boolean unionSet(int i, int j)
	{
		if (isSameSet(i, j))
			return false;
		numSets--;
		int x = findSet(i), y = findSet(j);
		col[y]=col[x];
		if(rank[x] > rank[y]) { p[y] = x; setSize[x] += setSize[y]; }
		else
		{	p[x] = y; setSize[y] += setSize[x];
			if(rank[x] == rank[y]) rank[y]++;
		}
		return true;
	}
	static void main() throws Exception{
		int q=sc.nextInt();
		HashMap<Integer,Integer>colToNode=new HashMap<>();
		preDSU(q+7);
		LinkedList<Integer>indices=new LinkedList<>();
		for(int i=0;i<q;i++){
			if(sc.nextInt()==1){
				indices.add(i);
				int col=sc.nextInt();
				addNode(i,col);
				if(colToNode.containsKey(col)){
					unionSet(colToNode.get(col),i);
				}
				colToNode.put(col,findSet(i));
			}
			else{
				int x=sc.nextInt(),y=sc.nextInt();
				if(!colToNode.containsKey(x))continue;
				if(!colToNode.containsKey(y)){
					addNode(i,y);
					colToNode.put(y,i);
				}
				unionSet(colToNode.get(y),colToNode.get(x));
				colToNode.put(y,findSet(colToNode.get(y)));
				colToNode.remove(x);
			}
		}
		while(!indices.isEmpty())pw.print(col[findSet(indices.pollFirst())]+" ");
	}
	public static void main(String[] args) throws Exception{
		sc=new MScanner(System.in);
//		sc=new MScanner(" .in");
		pw = new PrintWriter(System.out);
		int tc=1;
//        tc=sc.nextInt();
		for(curt=1;curt<=tc;curt++) {
//			pw.printf("Case #%d:", curt);
			main();
		}

		pw.flush();
	}
	static int curt;
	static PrintWriter pw;
	static MScanner sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
			int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
			return in;
		}
		public long[] longArr(int n) throws IOException {
			long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
			return in;
		}
		public int[] intSortedArr(int n) throws IOException {
			int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}
		public long[] longSortedArr(int n) throws IOException {
			long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
			Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
			return in;
		}
		public Long[] LongArr(int n) throws IOException {
			Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
			return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}

	}
	static void dbg(int[]in) {
		System.out.println(Arrays.toString(in));
	}
	static void dbg(long[]in) {
		System.out.println(Arrays.toString(in));
	}
	static void sort(int[]in) {
		shuffle(in);
		Arrays.sort(in);
	}
	static void sort(long[]in) {
		shuffle(in);
		Arrays.sort(in);
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}