#include<iostream> #include<cstdio> #define N 100005 using namespace std; int n,m,sz,rt,c[N][2],fa[N],s[N],rev[N]; inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } void update(int x){ s[x]=s[c[x][0]]+s[c[x][1]]+1; } void rotate(int x,int &k){ int y=fa[x],z=fa[y],l,r; if(c[y][0]==x)l=0;else l=1;r=l^1; if(y==k)k=x; else{ if(c[z][0]==y)c[z][0]=x; else c[z][1]=x; } fa[y]=x;fa[x]=z;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; update(y);update(x); } void splay(int x,int &k){ int y,z; while(x!=k){ y=fa[x];z=fa[y]; if(y!=k){ if((c[y][0]==x)^(c[z][0]==y))rotate(x,k); else rotate(y,k); } rotate(x,k); } } void pushdown(int x){ int l=c[x][0],r=c[x][1]; if(rev[x]){ swap(c[x][0],c[x][1]); if(l)rev[l]^=1; if(r)rev[r]^=1; rev[x]=0; } } void build(int l,int r,int last){ if(l>r)return; if(l==r){ s[l]=1;fa[l]=last; if(l<last)c[last][0]=l; else c[last][1]=l; return; } int mid=(l+r)>>1; build(l,mid-1,mid);build(mid+1,r,mid); fa[mid]=last;update(mid); if(mid<last)c[last][0]=mid; else c[last][1]=mid; } int find(int x,int rk){ pushdown(x); int l=c[x][0],r=c[x][1]; if(s[l]+1==rk)return x; else if(s[l]>=rk)return find(l,rk); else return find(r,rk-s[l]-1); } void rever(int l,int r){ int x=find(rt,l),y=find(rt,r+2); splay(x,rt);splay(y,c[x][1]); rev[c[y][0]]^=1; } int main(){ n=read();m=read(); rt=(n+3)>>1; build(1,n+2,0); for(int i=1;i<=m;i++){ int a,b; a=read();b=read(); rever(a,b); } for(int i=2;i<=n+1;i++) printf("%d ",find(rt,i)-1); return 0; }