#include <cstring>
#include <list>
#include<algorithm>
const int N = 1.5e5+10;

using namespace std;
list<int> d[N];


int main() {
   int n, m;
   while((scanf("%d%d", &n, &m)) != EOF)
   {
       for(int i = 1; i <= n; i++)
           d[i].clear();
        int k,u,val,w,v;
        while(m--)
        {
            scanf("%d",&k);
            switch(k)
            {
            case 1:
                scanf("%d%d%d",&u,&w,&val);
                if(w == 0) d[u].push_front(val);
                else if(w == 1) d[u].push_back(val);
                break;
            case 2:
                scanf("%d%d",&u,&w);
                if(d[u].empty())
                    printf("-1\n");
                else{
                    if(w == 0)
                    {
                        printf("%d\n",d[u].front());
                        d[u].pop_front();
                    }
                    else if(w == 1)
                    {
                        printf("%d\n",d[u].back());
                        d[u].pop_back();
                    }
                    }
                    break;
            case 3:
                scanf("%d%d%d",&u,&v,&w);
                if(w == 0)
                   d[u].insert(d[u].end(),d[v].begin(), d[v].end());
                else if(w == 1)
                {
                    reverse(d[v].begin(), d[v].end());
                    d[u].insert(d[u].end(),d[v].begin(), d[v].end());
                }
                d[v].clear();
                break;
            }
        }

   }

   return 0;
}