#include <bits/stdc++.h>
using namespace std;
int x,p,arr[200002];
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>x>>p;
	q.push(x);
	for(int i=1;i<=p;i++){
		int a,b;
		cin>>a>>b;
		q.push(a);
		q.push(b);
		int l=q.size()/2;
		int op=1;
		while(!q.empty() && q.size()!=l+1){
			arr[op]=q.top();
			q.pop();
			op++;
		}
		cout<<q.top()<<"\n";
		for(int i=1;i<=op-1;i++){
			q.push(arr[i]);
		}
	}
	return 0;
}
/*
奇数个：中位数是第 (n+1)/2 个数据，例如 5 个数据取第 3 个 。
o(n(n/2)
偶数个：中位数是第 n/2 个和第 (n/2+1) 个数据的平均数，例如 4 个数据取第 2、3 个的平均值 。
*/