用stl的list即可，注意。。。代码的简洁性（被debug伤痛）注意合并时可以手动pop,或者用splice进行合并，不能用merge！！！merge合并是自带排序！！！

#include<bits/stdc++.h>
#include<deque>
using namespace std;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';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[150005];
        while(q--)
        {
            cmd=read();
            if(cmd==1)
            {
                u=read();w=read();val=read();
                if (w)
                {
                    que[u].push_back(val);
                }
                else
                {
                    que[u].push_front(val);
                }
            }
            else if (cmd==2)
            {
                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==0){
                     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 0;
}