#include<bits/stdc++.h>

#include<deque>

using namespace std;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

std::list<int>::iterator it;

int main()

{

    int n,q,cmd;

    int u,w,val,s,v;

    int ans;

    while(~scanf("%d%d",&n,&q))

    {

        list<int>que[];

        while(q--)

        {

            cmd=read();

            if(cmd==)

            {

                u=read();w=read();val=read();

                if (w)

                {

                    que[u].push_back(val);

                }

                else

                {

                    que[u].push_front(val);

                }

            }

            else if (cmd==)

            {

                u=read();

                w=read();

                if (w)

                {

                    if (que[u].empty())

                    {

                        printf("-1\n");

                        continue;

                    }

                        ans=que[u].back();

                        printf("%d\n",ans);

                        que[u].pop_back();

                }

                else

                {

                    if (que[u].empty())

                    {

                        printf("-1\n");

                        continue;

                    }

                        ans=que[u].front();

                        printf("%d\n",ans);

                        que[u].pop_front();

                }

            }

            else {

                u=read();

                v=read();

                w=read();

                int temp;

                if (w==){

                     it=que[u].end();

                     que[u].splice(it,que[u]);

                }else {

                     it=que[u].end();

                     que[v].reverse();

                     que[u].splice(it,que[v]);

                }

            }

        }

    }

    return ;

}