12356 - Army Buddies

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int s, b, l, r;
    while (cin >> s >> b, s || b) {
        set<int> st;
        for (int i = 1; i <= s; i++) st.insert(i);
        for (int i = 0; i < b; i++) {
            cin >> l >> r;
            for (int j = l; j <= r; j++) st.erase(j);
            auto it1 = st.lower_bound(l);
            auto it2 = st.lower_bound(r);
            if (it1 != st.begin()) {
                it1--;
                if (it1 != st.end()) {
                    cout << *it1;
                }
                else cout << "*";
            }
            else cout << "*";

            cout << " ";
            if (it2 != st.end()) cout << *it2;
            else cout << "*";
            cout << endl;
        }
        cout << "-\n";
    }
}