#include<bits/stdc++.h>
using namespace std;
long long int a[500005],b[500005],c[500005];
#define M 998244353
struct Node{
    int info;
    Node* left;
    Node* right;
    int child;
};
int Inorder(Node *cur,int z) {
  //if (z==0) return cur->info;
  int x=0;
  if(cur->left!=nullptr)x=cur->left->child;
 // cout<<x<<endl;
  if(cur->left!=nullptr&&cur->left->child>=z)
  {
      return Inorder(cur->left,z);
  }
  else if(x+1==z)return cur->info;
  else return Inorder(cur->right,z-x-1);
}
Node* getpos(Node* cur,int val)
{
    cur->child++;
    if(cur->info>val)
    {
        if(cur->left==nullptr)return cur;
        return getpos(cur->left,val);
    }
    else
    {
        if(cur->right==nullptr)return cur;
        return getpos(cur->right,val);
    }
}
int main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     long long int t,i,j,k,w,y,z,n,m,x,l,r;
     cin>>x>>n;
     z=1;
     Node* root=new Node;
     root->info=x;
     root->left=nullptr;
     root->right=nullptr;
     root->child=1;
     for(i=1;i<=n;i++)
     {
         cin>>x>>y;
         Node* cur=new Node;
         cur->info=x;
         cur->child=1;
         cur->left=nullptr;
         cur->right=nullptr;
         Node* pos=getpos(root,x);
         if(pos->info>x)
         {
             pos->left=cur;
         }
         else
         {
             pos->right=cur;
         }
         Node* cur1=new Node;
         cur1->info=y;
         cur1->child=1;
         cur1->left=nullptr;
         cur1->right=nullptr;
         Node* pos1=getpos(root,y);
         if(pos1->info>y)
         {
             pos1->left=cur1;
         }
         else
         {
             pos1->right=cur1;
         }
         z++;
         cout<<Inorder(root,z)<<endl;
     }
}