#include<iostream>

using namespace std;

int n ,x ,y ,num = 1,first = 1;
int f;
struct node{
	int val;
	int next;
}lis[1000010];
int main(){
	lis[num].val = 1;
	lis[num].next = 0;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> f;
		if(f == 1){
			cin >> x >> y;
			int id = first;
			while(id != 0){
				if(lis[id].val == x){
					num++;
					lis[num].val = y;
					lis[num].next = lis[id].next;
					lis[id].next = num;
					break;
				}else {
					id = lis[id].next;
				}
			}
		} else if(f == 2) {
			cin >> x;
			int id = first;
			while(id != 0){
				if(lis[id].val == x){
					if(lis[id].next == 0){
						cout << '0' << endl;
					}else {
						int tmp  = lis[id].next;
						cout << lis[tmp].val << endl;
					}
					break;
				}else {
					id = lis[id].next;
				}
			}
		} else if(f == 3) {
			cin >> x;
			int id = first;
			while(id != 0){
				if(lis[id].val == x){
					if(lis[id].next == 0){
						break;
					} else {
						int tmp = lis[id].next;
						int tmp2 = lis[tmp].next;
						lis[id].next = tmp2;
					}
					break;
				} else {
					id=lis[id].next;
				}
			}
		}
	}
	return 0;
}