using namespace std;
#include <iostream>
//###INSERT CODE HERE -
struct NODE
{
    int info;
    NODE* pNext;
};
struct  LIST
{
    NODE* pHead;
    NODE* pTail;
};
void CreateList(LIST &L);
NODE* CreateNode(int x)
{
  NODE *p;
  p = new NODE;
  p->info = x;
  p->pNext = NULL;
  return p;
};
void addTail(LIST &L)
{
    int x;
    cin>>x;
    NODE *p = CreateNode(x);
    if(L.pHead == NULL)
    {
        L.pHead = p;
        L.pTail = p;
    }
    else {
        L.pTail->pNext = p;
        L.pTail = p;
    };
    CreateList(L);
};
void addHead(LIST &L)
{
    int x;
    cin>>x;
    NODE *p = CreateNode(x);
    if(L.pHead == NULL)
    {
        L.pHead = p;
        L.pTail = p;
    }
    else {
        p->pNext = L.pHead;
        L.pHead = p;
    };
    CreateList(L);
};
void add_afterX_1(LIST &L){
    int Y,X;
    cin>>X>>Y;
    NODE* p = L.pHead;
    while(p!=NULL && p->info !=X){
        p=p->pNext;// pinfo = 3
    }
    if(p!=NULL && p->info == X){
        NODE* q = CreateNode(Y);
        if(L.pTail == p){
            L.pTail->pNext = q;
            L.pTail = q;// 1 2 3 0 4 5
        }
        else {
            q->pNext = p->pNext;
            p->pNext = q;
        }
    }
    CreateList(L);
}
void CreateList(LIST &L) {
    int a;
    cin>>a;
    if(a!=-1){
        if(a==0){
        addHead(L);
        //CreateList(L);
        }
         if(a==1){
            addTail(L);
            //CreateList(L);
        }
        if(a==2){
            add_afterX_1(L);
            //CreateList(L);
        }
    }
}
void PrintList(LIST L){
    NODE *head=L.pHead;
    if(head==NULL)
        cout<<"Empty List.";
    while(head!=NULL){
        cout<<head->info<<" ";
        head = head->pNext;
    }
}