1 #include <cstdio>
 2 #include <cstring>
 3 #include <ctime>
 4 #include <cstdlib>
 5 #include <iostream>
 6 using namespace std;
 7 const int N=100100;
 8 int n;
 9 struct Treap
10 {
11     Treap *ch[2];
12     int val,key,flip,size;
13     Treap(){size=flip=val=0;key=rand();ch[0]=ch[1]=NULL;}
14     inline void update()
15         {size=ch[0]->size+1+ch[1]->size;}
16 }*null=new Treap(),*root=null,*stack[N],*x,*last;
17 typedef pair<Treap*,Treap*> D;
18 inline Treap* newTreap(int val)
19 {
20     Treap *o=new Treap();
21     o->size=1;o->val=val;
22     o->ch[0]=o->ch[1]=null;
23     return o;
24 }
25 inline void pushdown_flip(Treap *o)
26 {
27     if(o==null)return;
28     if(o->flip)
29     {
30         o->flip^=1;
31         if(o->ch[0]!=null)o->ch[0]->flip^=1;
32         if(o->ch[1]!=null)o->ch[1]->flip^=1;
33         swap(o->ch[0],o->ch[1]);
34     }
35 }
36 Treap* merge(Treap *a,Treap *b)
37 {
38     if(a==null)return b;
39     if(b==null)return a;
40     pushdown_flip(a);pushdown_flip(b);
41     if(a->key < b->key)
42         {a->ch[1]=merge(a->ch[1],b);a->update();return a;}
43     else 
44         {b->ch[0]=merge(a,b->ch[0]);b->update();return b;}
45 }
46 D split(Treap *o,int k)
47 {
48     if(o==null)return D(null,null);
49     pushdown_flip(o);D y;
50     if(o->ch[0]->size>=k)
51         {y=split(o->ch[0],k);o->ch[0]=y.second;o->update();y.second=o;}
52     else
53         {y=split(o->ch[1],k-o->ch[0]->size-1);o->ch[1]=y.first;o->update();y.first=o;}
54     return y;
55 }
56 inline Treap* build()
57 {
58     int p=0;
59     for(int i=1;i<=n;i++)
60     {
61         x=newTreap(i);last=null;
62         while(p&&stack[p]->key > x->key)
63             {stack[p]->update();last=stack[p];stack[p--]=null;}
64         if(p)stack[p]->ch[1]=x;
65         x->ch[0]=last;stack[++p]=x;
66     }
67     while(p)stack[p--]->update();
68     return stack[1];
69 }
70 inline void dfs(Treap *o)
71 {
72     if(o==null)return;
73     pushdown_flip(o);
74     if(o->ch[0]!=null)dfs(o->ch[0]);
75     printf("%d ",o->val);
76     if(o->ch[1]!=null)dfs(o->ch[1]);
77 }
78 inline void reserve()
79 {
80     int l,r;scanf("%d%d",&l,&r);
81     D x=split(root,r);
82     D y=split(x.first,l-1);
83     if(y.second!=null)y.second->flip^=1;
84     root=merge(merge(y.first,y.second),x.second);
85 }
86 int main()
87 {
88     int m;scanf("%d%d",&n,&m);
89     root=build();
90     while(m--)reserve();
91     dfs(root);
92 }