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

#define fastio ios::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back

#define ll long long
#define int long long

#define f first
#define s second

const int INF = 1e18;
const int MOD = 1e9 + 7;

template<typename T>
bool chmin(T &a, T b) {
    if (a > b) { a = b; return true; }
    return false;
}

template<typename T>
bool chmax(T &a, T b) {
    if (a < b) { a = b; return true; }
    return false;
}

template<typename T>
istream& operator>>(istream &is, vector<T> &v) {
    for (auto &x : v) is >> x;
    return is;
}

template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) {
    for (auto &x : v) os << x << " ";
    return os;
}

#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << x << '\n'
#else
#define dbg(x)
#endif

void tc() {
    int x;
    cin>>x;
    int q;
    cin>>q;
    priority_queue<int>left;
    priority_queue<int, vector<int>, greater<int>>right;

    left.push(x);
    while(q--){
        int a,b;
        cin>>a>>b;
        if(left.top() >= a)left.push(a);
        else right.push(a);
        if(left.top() >= a)left.push(b);
        else right.push(b);
        if(left.size() > right.size()){
            while(left.size() != right.size()+1){
                right.push(left.top());
                left.pop();
            }
        }else{
            while(left.size() != right.size()+1){
                left.push(right.top());
                right.pop();
            }
        }
        cout<<left.top()<<"\n";
    }
}

int32_t main() {
    fastio;

    int tt = 1;
    // cin >> tt;
    while (tt--) {
        tc();
    }

    return 0;
}