rt

#include<bits/stdc++.h>
using namespace std;

struct Fhq_Treap{
	int l;
	int r;
	int sz;
	int key;
	int val;
	int lazy;
}tr[114514];

int num=0,root=0,a[114514];

int built_node(int v){
	tr[++num].val=v;
	tr[num].key=rand();
	tr[num].sz=1;
	tr[num].l=0;
	tr[num].r=0;
	tr[num].lazy=0;
	return num;
}

void push_up(int now){
	tr[now].sz=tr[tr[now].l].sz+tr[tr[now].r].sz+1;
}

void swp(int x,int y){
	swap(tr[x].key,tr[y].key);
	swap(tr[x].l,tr[y].l);
	swap(tr[x].r,tr[y].r);
	swap(tr[x].lazy,tr[y].lazy);
	swap(tr[x].sz,tr[y].sz);
	swap(tr[x].val,tr[y].val);
}

void push_down(int now){
	swp(tr[now].l,tr[now].r);
	if(tr[now].l)tr[tr[now].l].lazy^=1;
	if(tr[now].r)tr[tr[now].r].lazy^=1;
	tr[now].lazy=0;
}

void split(int now,int v,int &x,int &y){
	if(!now){
		x=y=0;return;
	}
	if(tr[now].lazy)push_down(now);
	if(tr[tr[now].l].sz<v){
		x=now;
		split(tr[x].r,v-tr[tr[now].l].sz-1,tr[x].r,y);
	}
	else{
		y=now;
		split(tr[y].l,v,x,tr[y].l);
	}
	push_up(now);
}

int merge(int x,int y){
	if(!x||!y){
		return x+y;
	}
	if(tr[x].key<tr[y].key){
		if(tr[x].lazy)push_down(x);
		tr[x].r=merge(tr[x].r,y);
		push_up(x);
		return x;
	}
	else{
	    if(tr[y].lazy)push_down(y);
		tr[y].l=merge(x,tr[y].l);
		push_up(y);
		return y;
	}
}

void outp(int now){
	if(!now)return;
	if(tr[now].lazy)push_down(now);
	outp(tr[now].l);
	cout<<now<<" "<<tr[now].val<<endl;
	outp(tr[now].r);
}

int main(){
	srand(114514);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		root=merge(root,built_node(i));
	}
	for(int i=1;i<=m;i++){
		int a,b,c,l,r;
		cin>>l>>r;
		split(root,l-1,a,b);
		split(b,r-l+1,b,c);
		//cout<<a<<" "<<b<<" "<<c;
		tr[b].lazy^=1;
		root=merge(a,merge(b,c));
		cout<<"*"<<endl; 
		for(int i=1;i<=n;i++){
		cout<<tr[i].l<<" "<<tr[i].r;
		cout<<endl;
	}
	outp(root);
	cout<<"*"<<endl;
	}
	outp(root);
}