1 var  2    i,j,k,l,m,n,head,a1,a2:longint;  3    s1:ansistring;  4    a,b,c,d,fat,lef,rig:array[0..200000] of longint;  5 procedure swap(var x,y:longint);inline;  6           var z:longint;  7           begin  8                z:=x;x:=y;y:=z;  9           end; 10  11 procedure ext(x:longint);inline; 12           begin 13                if (x=0) then exit; 14                if c[x]=0 then exit; 15                swap(lef[x],rig[x]); 16                c[x]:=0; 17                c[lef[x]]:=1-c[lef[x]]; 18                c[rig[x]]:=1-c[rig[x]]; 19                c[0]:=0; 20           end; 21 procedure rt(x:longint);inline; 22           var f,l:longint; 23           begin 24                if x=0 then exit; 25                ext(x); 26                if lef[x]=0 then exit; 27                ext(lef[x]); 28                f:=x;l:=lef[x]; 29                b[lef[x]]:=b[x]; 30                b[x]:=b[rig[x]]+1+b[rig[l]]; 31                lef[x]:=rig[l]; 32                fat[rig[l]]:=x; 33                rig[l]:=x; 34                fat[l]:=fat[x]; 35                fat[x]:=l; 36                if rig[fat[l]]=x then rig[fat[l]]:=l; 37                if lef[fat[l]]=x then lef[fat[l]]:=l; 38                fat[0]:=0; 39           end; 40 procedure lt(x:longint);inline; 41           var f,r:longint; 42           begin 43                if x=0 then exit; 44                ext(x);if rig[x]=0 then exit; 45                ext(rig[x]); 46                f:=x;r:=rig[x]; 47                b[rig[x]]:=b[x]; 48                b[x]:=1+b[lef[x]]+b[lef[r]]; 49                rig[x]:=lef[r]; 50                fat[lef[r]]:=x; 51                lef[r]:=x; 52                fat[r]:=fat[x]; 53                fat[x]:=r; 54                if rig[fat[r]]=x then rig[fat[r]]:=r; 55                if lef[fat[r]]=x then lef[fat[r]]:=r; 56                fat[0]:=0; 57           end; 58 procedure ins(x,y:longint);inline; 59           begin 60                if a[y]<a[x] then 61                   begin 62                        if lef[x]=0 then 63                           begin 64                                lef[x]:=y; 65                                fat[y]:=x; 66                           end 67                        else ins(lef[x],y); 68                   end 69                else 70                    begin 71                         if rig[x]=0 then 72                            begin 73                                 rig[x]:=y; 74                                 fat[y]:=x; 75                            end 76                         else ins(rig[x],y); 77                    end; 78                b[x]:=1+b[lef[x]]+b[rig[x]]; 79           end; 80 procedure up2(var x:longint);inline; 81           begin 82                if (fat[x]=0) or (x=0) then exit; 83                if lef[fat[x]]=x then 84                   begin 85                        if lef[fat[fat[x]]]=fat[x] then 86                           begin 87                                rt(fat[fat[x]]); 88                                rt(fat[x]); 89                           end 90                        else 91                            begin 92                                 rt(fat[x]); 93                                 lt(fat[x]); 94                            end; 95                   end 96                else 97                    begin 98                         if rig[fat[fat[x]]]=fat[x] then 99                            begin100                                 lt(fat[fat[x]]);101                                 lt(fat[x]);102                            end103                         else104                             begin105                                  lt(fat[x]);106                                  rt(fat[x]);107                             end;108                    end;109           end;110 procedure up1(x:longint);inline;111           begin112                if (x=0) or (fat[x]=0) then exit;113                if lef[fat[x]]=x then rt(fat[x]) else lt(fat[x]);114           end;115 procedure splay(x:longint);inline;116           begin117                if (x=0) or (fat[x]=0) then exit;118                while fat[fat[x]]>0 do119                      up2(x);120                if fat[x]>0 then up2(x);121                head:=x;122           end;123 procedure splay2(x:longint);inline;124           begin125                if (x=0) or (fat[x]=0) then exit;126                while fat[fat[fat[x]]]>0 do127                      up2(x);128                if fat[fat[x]]>0 then up1(x);129           end;130 function getrank(x,y:longint):longint;inline;131          begin132               if (x=0) then exit(0);133               ext(x);134               if (b[lef[x]]+1)=y then exit(x);135               if (b[lef[x]]+1)>y then exit(getrank(lef[x],y)) else exit(getrank(rig[x],y-1-b[lef[x]]));136          end;137 procedure turn(x,y:longint);inline;138           var a1,a2:longint;139           begin140                if (x=1) and (y=n) then141                   c[head]:=1-c[head]142                else143                    begin144                         if (x=1) then145                            begin146                                 a1:=getrank(head,y+1);147                                 splay(a1);148                                 ext(a1);149                                 c[lef[a1]]:=1-c[lef[a1]];150                            end151                         else152                             begin153                                  if (y=n) then154                                     begin155                                          a2:=getrank(head,x-1);156                                          splay(a2);157                                          ext(a2);158                                          c[rig[a2]]:=1-c[rig[a2]];159                                     end160                                  else161                                      begin162                                           a1:=getrank(head,x-1);163                                           a2:=getrank(head,y+1);164                                           splay(a2);splay2(a1);165                                           ext(a2);ext(a1);166                                           c[rig[a1]]:=1-c[rig[a1]];167                                      end;168                             end;169                    end;170           end;171 function showoff(x:longint):ansistring;inline;172          var s1:ansistring;173          begin174               if x=0 then exit(‘‘);175               ext(x);176               str(x,s1);177               exit(showoff(lef[x])+s1+‘ ‘+showoff(rig[x]));178          end;179 begin180      readln(n,m);181      for i:=1 to n do182          begin183               a[i]:=i;c[i]:=0;b[i]:=1;184          end;185      head:=1;186      for i:=2 to n do187          begin188               ins(head,i);189               splay(random(i)+1);190          end;191      for i:=1 to m do192          begin193               readln(a1,a2);194               turn(a1,a2);195          end;196      s1:=showoff(head);197      writeln(s1);198      readln;199 end.200