#include<bits/stdc++.h>
using namespace std;
list<int> l{1,0};
int main()
{
	int q,flag,x,y;
	scanf("%d",&q);
	while (q--)
	{
        scanf("%d",&flag);
		if (flag==1)
		{
			scanf("%d%d",&x,&y);
			auto it=l.begin(),jt=l.end();
			while (*it!=x&&*jt!=x)
			{
				it++;
				jt--;
			}
			if (*it==x)
			{
                l.insert(++it,y);
			}
			else
			{
			    l.insert(++jt,y);
			}
		}
		else if (flag==2)
		{
			scanf("%d",&x);
			auto it=l.begin(),jt=l.end();
			while (*it!=x&&*jt!=x)
			{
				it++;
				jt--;
			}
			if (*it==x)
			{
				printf("%d\n",*(++it));
			}
			else
			{
                printf("%d\n",*(++jt));
			}
		}
		else
		{
		    scanf("%d",&x);
			auto it=l.begin(),jt=l.end();
			while (*it!=x&&*jt!=x)
			{
				it++;
				jt--;
			}
			if (*it==x)
			{
                l.erase(++it);
			}
			else
			{
			    l.erase(++jt);
			}
		}
	}
	return 0;
}