// God be praised
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node {
int freq[9], i, lazy;
node () {
fill(freq, freq + 9, 0);
i = lazy = 0;
}
} tree[4*N];
void build (int idx, int nl, int nr) {
tree[idx].freq[1] = (nr - nl) + 1;
if (nl == nr) return;
int mid = (nl + nr) / 2;
build(idx*2+1, nl, mid);
build(idx*2+2, mid+1, nr);
}
void update (node &p, node &child) {
int j = 0;
for (int i = child.i; i < 9; i++, j++) {
p.freq[j] += child.freq[i];
}
for (int i = 0; i < child.i; i++, j++) {
p.freq[j] += child.freq[i];
}
}
void update (int idx) {
node &p = tree[idx];
fill(p.freq, p.freq + 9, 0);
p.i = 0;
update(p, tree[idx*2+1]);
update(p, tree[idx*2+2]);
}
void add (int &a, int b) {
a += b;
if (a >= 9) {
a -= 9;
}
}
void dec (int &a, int b) {
a -= b;
if (a < 0) {
a += 9;
}
}
void propagate (int idx, int nl, int nr) {
node &p = tree[idx];
if (p.lazy && (nl < nr)) {
node &l = tree[idx*2+1];
add(l.lazy, p.lazy);
dec(l.i, p.lazy);
node &r = tree[idx*2+2];
add(r.lazy, p.lazy);
dec(r.i, p.lazy);
p.lazy = 0;
}
}
int fquery[9];
void query (int idx, int nl, int nr, int ql, int qr) {
if (nl > qr || ql > nr) return;
node &p = tree[idx];
if (nl >= ql && nr <= qr) {
int j = 0;
for (int i = p.i; i < 9; i++, j++) {
fquery[j] += p.freq[i];
}
for (int i = 0; i < p.i; i++, j++) {
fquery[j] += p.freq[i];
}
return;
}
propagate(idx, nl, nr);
int mid = (nl + nr) / 2;
query(idx*2+1, nl, mid, ql, qr);
query(idx*2+2, mid+1, nr, ql, qr);
}
void chord (int idx, int nl, int nr, int ql, int qr, int note) {
if (nl > qr || ql > nr) return;
if (nl >= ql && nr <= qr) {
node &p = tree[idx];
add(p.lazy, note);
dec(p.i, note);
return;
}
propagate(idx, nl, nr);
int mid = (nl + nr) / 2;
chord(idx*2+1, nl, mid, ql, qr, note);
chord(idx*2+2, mid+1, nr, ql, qr, note);
update(idx);
}
int ans[] = { 1, 0, 8, 7, 6, 5, 4, 3, 2 };
void show (int idx, int nl, int nr) {
node &p = tree[idx];
if (nl == nr) {
printf("%d\n", ans[p.i]);
return;
}
propagate(idx, nl, nr);
int mid = (nl + nr) / 2;
show(idx*2+1, nl, mid);
show(idx*2+2, mid+1, nr);
}
int greatest () {
int mx = 0;
for (int i = 1; i < 9; i++) {
if (fquery[i] >= fquery[mx]) {
mx = i;
}
}
return mx;
}
int main () {
int n, q;
scanf("%d %d", &n, &q);
build(0, 0, n-1);
for (int i = 0, a, b; i < q; i++) {
scanf("%d %d", &a, &b);
fill(fquery, fquery + 9, 0);
query(0, 0, n-1, a, b);
int note = greatest();
if (note) chord(0, 0, n-1, a, b, note);
}
show(0, 0, n-1);
return 0;
}
Ly8gR29kIGJlIHByYWlzZWQKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTiA9IDFlNSArIDU7CnN0cnVjdCBub2RlIHsKCWludCBmcmVxWzldLCBpLCBsYXp5OwoKCW5vZGUgKCkgewoJCWZpbGwoZnJlcSwgZnJlcSArIDksIDApOwoJCWkgPSBsYXp5ID0gMDsKCX0KfSB0cmVlWzQqTl07Cgp2b2lkIGJ1aWxkIChpbnQgaWR4LCBpbnQgbmwsIGludCBucikgewoJdHJlZVtpZHhdLmZyZXFbMV0gPSAobnIgLSBubCkgKyAxOwoJCglpZiAobmwgPT0gbnIpIHJldHVybjsKCglpbnQgbWlkID0gKG5sICsgbnIpIC8gMjsKCWJ1aWxkKGlkeCoyKzEsIG5sLCBtaWQpOwoJYnVpbGQoaWR4KjIrMiwgbWlkKzEsIG5yKTsKfQoKdm9pZCB1cGRhdGUgKG5vZGUgJnAsIG5vZGUgJmNoaWxkKSB7CglpbnQgaiA9IDA7Cglmb3IgKGludCBpID0gY2hpbGQuaTsgaSA8IDk7IGkrKywgaisrKSB7CgkJcC5mcmVxW2pdICs9IGNoaWxkLmZyZXFbaV07Cgl9Cglmb3IgKGludCBpID0gMDsgaSA8IGNoaWxkLmk7IGkrKywgaisrKSB7CgkJcC5mcmVxW2pdICs9IGNoaWxkLmZyZXFbaV07Cgl9Cn0KCnZvaWQgdXBkYXRlIChpbnQgaWR4KSB7Cglub2RlICZwID0gdHJlZVtpZHhdOwoJZmlsbChwLmZyZXEsIHAuZnJlcSArIDksIDApOwoJcC5pID0gMDsKCgl1cGRhdGUocCwgdHJlZVtpZHgqMisxXSk7Cgl1cGRhdGUocCwgdHJlZVtpZHgqMisyXSk7Cn0KCnZvaWQgYWRkIChpbnQgJmEsIGludCBiKSB7CglhICs9IGI7CglpZiAoYSA+PSA5KSB7CgkJYSAtPSA5OwoJfQp9Cgp2b2lkIGRlYyAoaW50ICZhLCBpbnQgYikgewoJYSAtPSBiOwoJaWYgKGEgPCAwKSB7CgkJYSArPSA5OwoJfQp9Cgp2b2lkIHByb3BhZ2F0ZSAoaW50IGlkeCwgaW50IG5sLCBpbnQgbnIpIHsKCW5vZGUgJnAgPSB0cmVlW2lkeF07CgkKCWlmIChwLmxhenkgJiYgKG5sIDwgbnIpKSB7CgkJbm9kZSAmbCA9IHRyZWVbaWR4KjIrMV07CgkJYWRkKGwubGF6eSwgcC5sYXp5KTsKCQlkZWMobC5pLCBwLmxhenkpOwoKCQlub2RlICZyID0gdHJlZVtpZHgqMisyXTsKCQlhZGQoci5sYXp5LCBwLmxhenkpOwoJCWRlYyhyLmksIHAubGF6eSk7CgoJCXAubGF6eSA9IDA7Cgl9Cn0KCmludCBmcXVlcnlbOV07CnZvaWQgcXVlcnkgKGludCBpZHgsIGludCBubCwgaW50IG5yLCBpbnQgcWwsIGludCBxcikgewoJaWYgKG5sID4gcXIgfHwgcWwgPiBucikgcmV0dXJuOwoKCW5vZGUgJnAgPSB0cmVlW2lkeF07CgkKCWlmIChubCA+PSBxbCAmJiBuciA8PSBxcikgewoJCWludCBqID0gMDsKCQlmb3IgKGludCBpID0gcC5pOyBpIDwgOTsgaSsrLCBqKyspIHsKCQkJZnF1ZXJ5W2pdICs9IHAuZnJlcVtpXTsKCQl9CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBwLmk7IGkrKywgaisrKSB7CgkJCWZxdWVyeVtqXSArPSBwLmZyZXFbaV07CgkJfQoJCXJldHVybjsKCX0KCglwcm9wYWdhdGUoaWR4LCBubCwgbnIpOwoKCWludCBtaWQgPSAobmwgKyBucikgLyAyOwoJcXVlcnkoaWR4KjIrMSwgbmwsIG1pZCwgcWwsIHFyKTsKCXF1ZXJ5KGlkeCoyKzIsIG1pZCsxLCBuciwgcWwsIHFyKTsKfQoKdm9pZCBjaG9yZCAoaW50IGlkeCwgaW50IG5sLCBpbnQgbnIsIGludCBxbCwgaW50IHFyLCBpbnQgbm90ZSkgewoJaWYgKG5sID4gcXIgfHwgcWwgPiBucikgcmV0dXJuOwoKCWlmIChubCA+PSBxbCAmJiBuciA8PSBxcikgewoJCW5vZGUgJnAgPSB0cmVlW2lkeF07CgkJYWRkKHAubGF6eSwgbm90ZSk7CgkJZGVjKHAuaSwgbm90ZSk7CgkJcmV0dXJuOwoJfQoKCXByb3BhZ2F0ZShpZHgsIG5sLCBucik7CgoJaW50IG1pZCA9IChubCArIG5yKSAvIDI7CgljaG9yZChpZHgqMisxLCBubCwgbWlkLCBxbCwgcXIsIG5vdGUpOwoJY2hvcmQoaWR4KjIrMiwgbWlkKzEsIG5yLCBxbCwgcXIsIG5vdGUpOwoKCXVwZGF0ZShpZHgpOwp9CgppbnQgYW5zW10gPSB7IDEsIDAsIDgsIDcsIDYsIDUsIDQsIDMsIDIgfTsKCnZvaWQgc2hvdyAoaW50IGlkeCwgaW50IG5sLCBpbnQgbnIpIHsKCW5vZGUgJnAgPSB0cmVlW2lkeF07CgoJaWYgKG5sID09IG5yKSB7CgkJcHJpbnRmKCIlZFxuIiwgYW5zW3AuaV0pOwoJCXJldHVybjsKCX0KCglwcm9wYWdhdGUoaWR4LCBubCwgbnIpOwoKCWludCBtaWQgPSAobmwgKyBucikgLyAyOwoJc2hvdyhpZHgqMisxLCBubCwgbWlkKTsKCXNob3coaWR4KjIrMiwgbWlkKzEsIG5yKTsKfQoKaW50IGdyZWF0ZXN0ICgpIHsKCWludCBteCA9IDA7Cglmb3IgKGludCBpID0gMTsgaSA8IDk7IGkrKykgewoJCWlmIChmcXVlcnlbaV0gPj0gZnF1ZXJ5W214XSkgewoJCQlteCA9IGk7CgkJfQoJfQoJcmV0dXJuIG14Owp9CgppbnQgbWFpbiAoKSB7CglpbnQgbiwgcTsKCXNjYW5mKCIlZCAlZCIsICZuLCAmcSk7CgoJYnVpbGQoMCwgMCwgbi0xKTsKCglmb3IgKGludCBpID0gMCwgYSwgYjsgaSA8IHE7IGkrKykgewoJCXNjYW5mKCIlZCAlZCIsICZhLCAmYik7CgoJCWZpbGwoZnF1ZXJ5LCBmcXVlcnkgKyA5LCAwKTsKCQlxdWVyeSgwLCAwLCBuLTEsIGEsIGIpOwoJCWludCBub3RlID0gZ3JlYXRlc3QoKTsKCgkJaWYgKG5vdGUpIGNob3JkKDAsIDAsIG4tMSwgYSwgYiwgbm90ZSk7Cgl9CgoJc2hvdygwLCAwLCBuLTEpOwoKCXJldHVybiAwOwp9