#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int data;
	Node *good;
};
Node *p,*head,*r,*q,*li;
int main()
{
	int a,b,x,y;
	cin>>a;
	head=new Node;
	r=head;
	li=new Node;
	p=new Node;
	p->data=1;
	r->good=p;
	r=p;
	p->good=NULL;
	for(int i=1;i<=a;i++)
	{
		cin>>b;
		if(b==1)
		{
			cin>>x>>y;
			int pan=1;
			p=head->good;
			while(p->data!=x)
			{	
				if(p->good==NULL)
				{
					pan=0;
					break;
				}
				p=p->good;
			}
			if(pan)
			{
				q=new Node;
				if(p->data==r->data)
				{
					q->data=y;
					r->good=q;
					r=q;
					q->good=NULL;
				}
				else
				{
					q->data=y;
					q->good=p->good;
					p->good=q;
				}
			}
		}
		if(b==2)
		{
			cin>>x;
			p=head->good;
			while(p->data!=x&&p->data!=r->data)
			{
				p=p->good;
			}
			if(p->good!=NULL)
			{
				q=p->good;
				cout<<q->data<<endl;
			}
			else if(x==r->data)
			{
				cout<<"0"<<endl;
			}
			else
			{
				; 
			}
		}
		if(b==3)
		{
			int pan=0;
			cin>>x;
			p=head;
			while(p->data!=x)
			{	
				if(p->good==NULL)
				{
					pan=1;
					break;
				}
				li=p;
				p=p->good;
			}
			if(!pan)
			{
				if(p->good==NULL)
				{
					p->data=y;
					r->good=p;
					r=p;
				p->good=NULL;
				}
				else
				{
					li->good=li->good->good;
				}
			}
		}
	return 0;
}