#include <bits/stdc++.h>
using namespace std;
int x,p,zhong;
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int> q2;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>x>>p;
	zhong=x;
	for(int i=1;i<=p;i++){
		int a,b,sum=0;
		cin>>a>>b;
		if(a<x){
			q2.push(a);
		}else{
			q1.push(a);
			sum++;
		}
		if(b<x){
			q2.push(b);
		}else{
			q1.push(b);
			sum++;
		}
		if(sum==0){
			cout<<q2.top()<<"\n";
			q1.push(zhong);
			zhong=q2.top();
			q2.pop();
			
		}else if(sum==2){
			cout<<q1.top()<<"\n";
			q2.push(zhong);
			zhong=q1.top();
			q1.pop();
		}
		if(sum==1){
			cout<<zhong<<"\n";
		}
		
	}
	return 0;
}