#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define SZ(S) ((int) ((S).size()))
 
#define DEBUG(x) { cout << #x << " = " << x << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
 
int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL);
    cout << (fixed) << setprecision(6);
    int n, q;
    while (cin >> n >> q && n) {
        set<int> s; FOR(i,1,n) s.insert(i);
        while (q--) {
            int l, r; cin >> l >> r;
            auto from = s.lower_bound(l);
            auto to = s.upper_bound(r);
            s.erase(from, to);
 
            auto it = s.lower_bound(l);
            if (it == s.begin()) cout << '*' << ' ';
            else {
                --it;
                cout << *it << ' ';
            }
            it = s.upper_bound(r);
            if (it == s.end()) cout << '*' << "\n";
            else cout << *it << "\n";
        }
        cout << '-' << "\n";
    }
    return 0;
}
 
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIEZPUihpLGEsYikgZm9yKGludCBpPShhKSxfYj0oYik7IGk8PV9iOyBpKyspCiNkZWZpbmUgRk9SRChpLGEsYikgZm9yKGludCBpPShhKSxfYj0oYik7IGk+PV9iOyBpLS0pCiNkZWZpbmUgUkVQKGksYSkgZm9yKGludCBpPTAsX2E9KGEpOyBpPF9hOyBpKyspCiNkZWZpbmUgRUFDSChpdCxhKSBmb3IoX190eXBlb2YoYS5iZWdpbigpKSBpdCA9IGEuYmVnaW4oKTsgaXQgIT0gYS5lbmQoKTsgKytpdCkKI2RlZmluZSBTWihTKSAoKGludCkgKChTKS5zaXplKCkpKQoKI2RlZmluZSBERUJVRyh4KSB7IGNvdXQgPDwgI3ggPDwgIiA9ICIgPDwgeCA8PCBlbmRsOyB9CiNkZWZpbmUgUFIoYSxuKSB7IGNvdXQgPDwgI2EgPDwgIiA9ICI7IEZPUihfLDEsbikgY291dCA8PCBhW19dIDw8ICcgJzsgY291dCA8PCBlbmRsOyB9CiNkZWZpbmUgUFIwKGEsbikgeyBjb3V0IDw8ICNhIDw8ICIgPSAiOyBSRVAoXyxuKSBjb3V0IDw8IGFbX10gPDwgJyAnOyBjb3V0IDw8IGVuZGw7IH0KCmludCBtYWluKCkgewogICAgaW9zIDo6IHN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoTlVMTCk7CiAgICBjb3V0IDw8IChmaXhlZCkgPDwgc2V0cHJlY2lzaW9uKDYpOwogICAgaW50IG4sIHE7CiAgICB3aGlsZSAoY2luID4+IG4gPj4gcSAmJiBuKSB7CiAgICAgICAgc2V0PGludD4gczsgRk9SKGksMSxuKSBzLmluc2VydChpKTsKICAgICAgICB3aGlsZSAocS0tKSB7CiAgICAgICAgICAgIGludCBsLCByOyBjaW4gPj4gbCA+PiByOwogICAgICAgICAgICBhdXRvIGZyb20gPSBzLmxvd2VyX2JvdW5kKGwpOwogICAgICAgICAgICBhdXRvIHRvID0gcy51cHBlcl9ib3VuZChyKTsKICAgICAgICAgICAgcy5lcmFzZShmcm9tLCB0byk7CgogICAgICAgICAgICBhdXRvIGl0ID0gcy5sb3dlcl9ib3VuZChsKTsKICAgICAgICAgICAgaWYgKGl0ID09IHMuYmVnaW4oKSkgY291dCA8PCAnKicgPDwgJyAnOwogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIC0taXQ7CiAgICAgICAgICAgICAgICBjb3V0IDw8ICppdCA8PCAnICc7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaXQgPSBzLnVwcGVyX2JvdW5kKHIpOwogICAgICAgICAgICBpZiAoaXQgPT0gcy5lbmQoKSkgY291dCA8PCAnKicgPDwgIlxuIjsKICAgICAgICAgICAgZWxzZSBjb3V0IDw8ICppdCA8PCAiXG4iOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8ICctJyA8PCAiXG4iOwogICAgfQogICAgcmV0dXJuIDA7Cn0KCg==

MSAxCjEgMQoxMCA0CjIgNQo2IDkKMSAxCjEwIDEwCjUgMQoxIDEKMCAw

1 1
1 1
10 4
2 5
6 9
1 1
10 10
5 1
1 1
0 0