RT，照着 tiger0132 的日报学的 Splay

//2021/8/5

#include <cstdio>

#include <algorithm>

using namespace std;

const int ma=100005;

struct Splay
{
	int son[3];
	
	int val,fa;
	
	int size,cnt;
};

Splay node[ma];

int tag[ma];

int root,chd;

int n,m;

inline bool chk(int p)
{
	return node[node[p].fa].son[1]==p;
}

inline void PushUp(int p)
{
	node[p].size=node[node[p].son[0]].size+node[node[p].son[1]].size+node[p].cnt;
}

inline void Rotate(int p)
{
	int y=node[p].fa,k=chk(p),w=node[p].son[k^1];
	
	node[y].son[k]=w,node[w].fa=y;
	
	node[node[y].fa].son[chk(y)]=p,node[p].fa=node[y].fa;
	
	node[p].son[k^1]=y,node[y].fa=p;
	
	PushUp(y);
	
	PushUp(p); 
}

inline void splay(int p,int goal=0)
{
	while(node[p].fa!=goal)
	{
		int y=node[p].fa,z=node[y].fa;
		
		if(z!=goal)
		{
			if(chk(p)!=chk(y))
			{
				Rotate(y);
			}
			
			else
			{
				Rotate(p);
			}
		}
		
		Rotate(p);
	}
	
	if(goal==0)
	{
		root=p;
	}
}

inline void Find(int k)
{
	if(root==0)
	{
		return;
	}
	
	int cur=root;
	
	while(node[cur].son[k>node[cur].val]!=0 && k!=node[cur].val)
	{
		cur=node[cur].son[k>node[cur].val];
	}
	
	splay(cur);
}

inline void Insert(int k)
{
	int cur=root,p=0;
	
	while(cur!=0 && node[cur].val!=k)
	{
		p=cur;
		
		cur=node[cur].son[k>node[cur].val];
	}
	
	if(cur!=0)
	{
		node[cur].cnt++;
	}
	
	else
	{
		cur=++chd;
		
		if(p!=0)
		{
			node[p].son[k>node[cur].val]=cur;
		}
		
		node[cur].son[0]=node[cur].son[1]=0;
		
		node[cur].fa=p,node[cur].val=k;
		
		node[cur].size=node[cur].cnt=1;
	}
	
	splay(cur);
}

inline int kth(int rk)
{
	int cur=root;
	
	while(true)
	{
		if(node[cur].son[0]!=0 && node[node[cur].son[0]].size>=rk)
		{
			cur=node[cur].son[0];
		}
		
		else if(rk>node[node[cur].son[0]].size+node[cur].cnt)
		{
			rk=rk-node[node[cur].son[0]].size-node[cur].cnt;
			
			cur=node[cur].son[1];
		}
		
		else
		{
			splay(cur);
			
			return cur;
		}
	}
}

inline int GetPre(int val)
{
	Find(val);
	
	if(val>node[root].val)
	{
		return root;
	}
	
	int cur=node[root].son[0];
	
	while(node[cur].son[1]!=0)
	{
		cur=node[cur].son[1];
	}
	
	splay(cur);
	
	return cur;
}

inline int GetSucc(int val)
{
	Find(val);
	
	if(val<node[root].val)
	{
		return root;
	}
	
	int cur=node[root].son[1];
	
	while(node[cur].son[0]!=0)
	{
		cur=node[cur].son[0];
	}
	
	splay(cur);
	
	return cur;
}

inline void Remove(int val)
{
	int pre=GetPre(val),succ=GetSucc(val);
	
	splay(pre);
	
	splay(succ,pre);
	
	int del=node[succ].son[0];
	
	if(node[del].cnt>1)
	{
		node[del].cnt--;
		
		splay(del);
	}
	
	else
	{
		node[succ].son[0]=0;
	}
	
	PushUp(succ);
	
	PushUp(pre); 
}

inline void PushDown(int p)
{
	if(tag[p]!=0)
	{
		swap(node[p].son[0],node[p].son[1]);
		
		tag[node[p].son[0]]^=1;
		
		tag[node[p].son[1]]^=1;
		
		tag[p]=0; 
	}
}

inline void rev(int l,int r)
{
	int x=kth(l),y=kth(r+2);
	
	splay(x);
	
	splay(y,x);
	
	tag[node[y].son[0]]^=1; 
}

//中序遍历输出 
inline void print(int k)
{
	PushDown(k);
	
	if(node[k].son[0]!=0)
	{
		print(node[k].son[0]);
	}
	
	if(node[k].val!=0 && node[k].val<=n)
	{
		printf("%d ",node[k].val);
	}
	
	if(node[k].son[1]!=0)
	{
		print(node[k].son[1]);
	}
}

int main(void)
{
	//freopen("in.txt","r",stdin); 
	
	scanf("%d%d",&n,&m);
	
	for(register int i=0;i<=n+1;i++)
	{
		Insert(i);
	}
	
	while(m--)
	{
		int l,r;
		
		scanf("%d%d",&l,&r);
		
		rev(l,r);
	}
	
	print(root);
	
	return 0;
}