#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n[N], ne[N];
int head = -1, idx = 0;
vector<int> ans;

int fndx(int x)
{
	int ret_flag = -1;
	if (head == -1)
	{
		return ret_flag;
	}
	
	int i = head;
	while (i != -1)
	{
		if (n[i] == x)
		{
			ret_flag = i;
			break;
		}
		i = ne[i];
	}
	
	return ret_flag;
}
void f1(int x, int y)
{
	int idx_x = fndx(x);
	n[idx] = y;
	ne[idx] = ne[idx_x];
	ne[idx_x] = idx;
	idx++;
}
void f2(int x)
{
	int i_x = fndx(x);
	if(ne[i_x] == -1)
	{
		//puts("0");
		ans.push_back(0);
		return;
	}
	ans.push_back(n[ne[i_x]]);
	//printf("%d\n", n[ne[i_x]]);
}
void f3(int x)
{
	int i_x = fndx(x);
	if (ne[i_x] == -1)
	{
		return;
	}
	ne[i_x] = ne[ne[i_x]];
}

int main()
{
	n[idx] = 1;
	ne[idx] = head;
	head = idx;
	idx++;
	
//	cout << head << endl;
//	cout << idx << endl;

//	cout << fndx(1) << endl;



	int i, q;
	int fnc;
	int x, y;
	scanf("%d", &q);
	for (i = 0; i < q; i++)
	{
		scanf("%d", &fnc);
		if (fnc == 1)
		{
			scanf("%d%d", &x, &y);
			f1(x, y);
		}
		else if (fnc == 2)
		{
			scanf("%d", &x);
			f2(x);
		}
		else if (fnc == 3)
		{
			scanf("%d", &x);
			f3(x);
		}
	}
	
	for (i = 0; i < ans.size(); i++)
	{
		printf("%d\n", ans[i]);
	}
	
	system("pause");
	
	return 0;
}