#include <iostream>
#include <vector>
#include <cmath>
#define N_KEYS 9
using namespace std;
typedef vector<int> vi;
struct node {
// node.sum(delta) = sum of properties in path root to node
// 1) leaf value = mod_n_keys(leaf.sum(delta))
// 2) node index 0 = mod_n_keys(node.sum(delta))
int delta, last_calculated_shift;
vi freq;
node() : delta(0) {
freq.resize(N_KEYS);
}
};
int N;
vector<node> tree;
void print_sequence(int idx, int start, int end, int delta) {
int value = delta + tree[idx].delta;
if (start == end) {
cout << value % N_KEYS << endl;
return;
}
int mid = (start + end) >> 1;
print_sequence(idx*2+1, start, mid, value);
print_sequence(idx*2+2, mid+1, end, value);
}
int mod_n_keys(int v) {
v %= N_KEYS;
if (v < 0) {
v += N_KEYS;
}
return v;
}
void frequency(int idx, int start, int end, int A, int B, vi &frequencies, int shift, vi &nodes) {
if (A > end || B < start) {
return;
}
node &x = tree[idx];
shift += x.delta;
x.last_calculated_shift = shift;
// if [A,B] contains [start,end]
if (start >= A && end <= B) {
vi &arr = x.freq;
for (int i=0; i<N_KEYS; i++) {
frequencies[i] += arr[mod_n_keys(i - shift)];
}
nodes.push_back(idx);
return;
}
int mid = (start + end) >> 1;
frequency(idx*2+1, start, mid, A, B, frequencies, shift, nodes);
frequency(idx*2+2, mid+1, end, A, B, frequencies, shift, nodes);
}
int index_max_element(vi &f) {
int ans = 0;
for (int i=1, l=N_KEYS; i<l; i++) {
if (f[i] >= f[ans]) {
ans = i;
}
}
return ans;
}
void updateUpward(int idx, vi &diff) {
if (idx == 0) return;
idx = (idx-1)/2;
node &p = tree[idx];
vi &arr = p.freq;
for (int i=0; i<N_KEYS; i++) {
arr[mod_n_keys(i - p.last_calculated_shift)] += diff[i];
}
updateUpward(idx, diff);
}
void update(vi &nodes, int most_freq_note) {
for (int j=0, q=nodes.size(); j<q; j++) {
int idx = nodes[j];
node &x = tree[idx];
vi &arr = x.freq;
// set the difference of frequencies after this update
vi diff(N_KEYS);
for (int i=0; i<N_KEYS; i++) {
int y = mod_n_keys(i - x.last_calculated_shift); // arr[y] = valueAt_i
int newValueAt_i = arr[mod_n_keys(y - most_freq_note)];
diff[i] = newValueAt_i - arr[y];
}
// update node decoration
x.delta += most_freq_note;
// propagate "diff" difference array upwards
updateUpward(idx, diff);
}
}
void initial_values(int idx, int start, int end) {
int range = end - start + 1;
tree[idx].freq[1] = range; // Initially all notes are 1
if (range > 1) {
int mid = (start + end) >> 1;
initial_values(idx*2+1, start, mid);
initial_values(idx*2+2, mid+1, end);
}
}
void setup(int N) {
int size = 2 * pow(2, ceil(log2(N))) - 1;
tree.resize(size);
initial_values(0, 0, N-1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int Q;
cin >> N >> Q;
setup(N);
while (Q--) {
int A, B;
cin >> A >> B;
vi freq(N_KEYS, 0);
vi nodes;
frequency(0, 0, N-1, A, B, freq, 0, nodes);
int most_freq_note = index_max_element(freq);
if (most_freq_note) update(nodes, most_freq_note);
}
print_sequence(0, 0, N-1, 1);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y21hdGg+CiNkZWZpbmUgTl9LRVlTIDkKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CgpzdHJ1Y3Qgbm9kZSB7CiAgICAvLyBub2RlLnN1bShkZWx0YSkgPSBzdW0gb2YgcHJvcGVydGllcyBpbiBwYXRoIHJvb3QgdG8gbm9kZQogICAgLy8gMSkgbGVhZiB2YWx1ZSA9IG1vZF9uX2tleXMobGVhZi5zdW0oZGVsdGEpKQogICAgLy8gMikgbm9kZSBpbmRleCAwID0gbW9kX25fa2V5cyhub2RlLnN1bShkZWx0YSkpCiAgICBpbnQgZGVsdGEsIGxhc3RfY2FsY3VsYXRlZF9zaGlmdDsKICAgIHZpIGZyZXE7CiAgICAKICAgIG5vZGUoKSA6IGRlbHRhKDApIHsKICAgICAgICBmcmVxLnJlc2l6ZShOX0tFWVMpOwogICAgfQp9OwoKaW50IE47CnZlY3Rvcjxub2RlPiB0cmVlOwoKdm9pZCBwcmludF9zZXF1ZW5jZShpbnQgaWR4LCBpbnQgc3RhcnQsIGludCBlbmQsIGludCBkZWx0YSkgewogICAgaW50IHZhbHVlID0gZGVsdGEgKyB0cmVlW2lkeF0uZGVsdGE7CgogICAgaWYgKHN0YXJ0ID09IGVuZCkgewogICAgICAgIGNvdXQgPDwgdmFsdWUgJSBOX0tFWVMgPDwgZW5kbDsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgaW50IG1pZCA9IChzdGFydCArIGVuZCkgPj4gMTsKICAgIHByaW50X3NlcXVlbmNlKGlkeCoyKzEsIHN0YXJ0LCBtaWQsIHZhbHVlKTsKICAgIHByaW50X3NlcXVlbmNlKGlkeCoyKzIsIG1pZCsxLCBlbmQsIHZhbHVlKTsKfQoKaW50IG1vZF9uX2tleXMoaW50IHYpIHsKICAgIHYgJT0gTl9LRVlTOwogICAgaWYgKHYgPCAwKSB7CiAgICAgICAgdiArPSBOX0tFWVM7CiAgICB9CiAgICByZXR1cm4gdjsKfQoKdm9pZCBmcmVxdWVuY3koaW50IGlkeCwgaW50IHN0YXJ0LCBpbnQgZW5kLCBpbnQgQSwgaW50IEIsIHZpICZmcmVxdWVuY2llcywgaW50IHNoaWZ0LCB2aSAmbm9kZXMpIHsKICAgIGlmIChBID4gZW5kIHx8IEIgPCBzdGFydCkgewogICAgICAgIHJldHVybjsKICAgIH0KICAgIAogICAgbm9kZSAmeCA9IHRyZWVbaWR4XTsKICAgIHNoaWZ0ICs9IHguZGVsdGE7CiAgICB4Lmxhc3RfY2FsY3VsYXRlZF9zaGlmdCA9IHNoaWZ0OwoKICAgIC8vIGlmIFtBLEJdIGNvbnRhaW5zIFtzdGFydCxlbmRdCiAgICBpZiAoc3RhcnQgPj0gQSAmJiBlbmQgPD0gQikgewogICAgICAgIHZpICZhcnIgPSB4LmZyZXE7CgogICAgICAgIGZvciAoaW50IGk9MDsgaTxOX0tFWVM7IGkrKykgewogICAgICAgICAgICBmcmVxdWVuY2llc1tpXSArPSBhcnJbbW9kX25fa2V5cyhpIC0gc2hpZnQpXTsKICAgICAgICB9CgogICAgICAgIG5vZGVzLnB1c2hfYmFjayhpZHgpOwogICAgICAgIHJldHVybjsKICAgIH0KCiAgICBpbnQgbWlkID0gKHN0YXJ0ICsgZW5kKSA+PiAxOwogICAgZnJlcXVlbmN5KGlkeCoyKzEsIHN0YXJ0LCBtaWQsIEEsIEIsIGZyZXF1ZW5jaWVzLCBzaGlmdCwgbm9kZXMpOwogICAgZnJlcXVlbmN5KGlkeCoyKzIsIG1pZCsxLCBlbmQsIEEsIEIsIGZyZXF1ZW5jaWVzLCBzaGlmdCwgbm9kZXMpOwp9CgppbnQgaW5kZXhfbWF4X2VsZW1lbnQodmkgJmYpIHsKICAgIGludCBhbnMgPSAwOwogICAgZm9yIChpbnQgaT0xLCBsPU5fS0VZUzsgaTxsOyBpKyspIHsKICAgICAgICBpZiAoZltpXSA+PSBmW2Fuc10pIHsKICAgICAgICAgICAgYW5zID0gaTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gYW5zOwp9Cgp2b2lkIHVwZGF0ZVVwd2FyZChpbnQgaWR4LCB2aSAmZGlmZikgewogICAgaWYgKGlkeCA9PSAwKSByZXR1cm47CiAgICBpZHggPSAoaWR4LTEpLzI7CiAgICBub2RlICZwID0gdHJlZVtpZHhdOwogICAgdmkgJmFyciA9IHAuZnJlcTsKCiAgICBmb3IgKGludCBpPTA7IGk8Tl9LRVlTOyBpKyspIHsKICAgICAgICBhcnJbbW9kX25fa2V5cyhpIC0gcC5sYXN0X2NhbGN1bGF0ZWRfc2hpZnQpXSArPSBkaWZmW2ldOwogICAgfQogICAgCiAgICB1cGRhdGVVcHdhcmQoaWR4LCBkaWZmKTsKfQoKdm9pZCB1cGRhdGUodmkgJm5vZGVzLCBpbnQgbW9zdF9mcmVxX25vdGUpIHsKICAgIGZvciAoaW50IGo9MCwgcT1ub2Rlcy5zaXplKCk7IGo8cTsgaisrKSB7CiAgICAgICAgaW50IGlkeCA9IG5vZGVzW2pdOwogICAgICAgIG5vZGUgJnggPSB0cmVlW2lkeF07CiAgICAgICAgdmkgJmFyciA9IHguZnJlcTsKICAgICAgICAKICAgICAgICAvLyBzZXQgdGhlIGRpZmZlcmVuY2Ugb2YgZnJlcXVlbmNpZXMgYWZ0ZXIgdGhpcyB1cGRhdGUKICAgICAgICB2aSBkaWZmKE5fS0VZUyk7CiAgICAgICAgZm9yIChpbnQgaT0wOyBpPE5fS0VZUzsgaSsrKSB7CgogICAgICAgICAgICBpbnQgeSA9IG1vZF9uX2tleXMoaSAtIHgubGFzdF9jYWxjdWxhdGVkX3NoaWZ0KTsgLy8gYXJyW3ldID0gdmFsdWVBdF9pCiAgICAgICAgICAgIGludCBuZXdWYWx1ZUF0X2kgPSBhcnJbbW9kX25fa2V5cyh5IC0gbW9zdF9mcmVxX25vdGUpXTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGRpZmZbaV0gPSBuZXdWYWx1ZUF0X2kgLSBhcnJbeV07CiAgICAgICAgfQogICAgICAgIAogICAgICAgIC8vIHVwZGF0ZSBub2RlIGRlY29yYXRpb24KICAgICAgICB4LmRlbHRhICs9IG1vc3RfZnJlcV9ub3RlOwoKICAgICAgICAvLyBwcm9wYWdhdGUgImRpZmYiIGRpZmZlcmVuY2UgYXJyYXkgdXB3YXJkcwogICAgICAgIHVwZGF0ZVVwd2FyZChpZHgsIGRpZmYpOwogICAgfQp9Cgp2b2lkIGluaXRpYWxfdmFsdWVzKGludCBpZHgsIGludCBzdGFydCwgaW50IGVuZCkgewogICAgaW50IHJhbmdlID0gZW5kIC0gc3RhcnQgKyAxOwogICAgdHJlZVtpZHhdLmZyZXFbMV0gPSByYW5nZTsgLy8gSW5pdGlhbGx5IGFsbCBub3RlcyBhcmUgMQoKICAgIGlmIChyYW5nZSA+IDEpIHsKICAgICAgICBpbnQgbWlkID0gKHN0YXJ0ICsgZW5kKSA+PiAxOwogICAgICAgIGluaXRpYWxfdmFsdWVzKGlkeCoyKzEsIHN0YXJ0LCBtaWQpOwogICAgICAgIGluaXRpYWxfdmFsdWVzKGlkeCoyKzIsIG1pZCsxLCBlbmQpOwogICAgfQp9Cgp2b2lkIHNldHVwKGludCBOKSB7CiAgICBpbnQgc2l6ZSA9IDIgKiBwb3coMiwgY2VpbChsb2cyKE4pKSkgLSAxOwogICAgdHJlZS5yZXNpemUoc2l6ZSk7CiAgICAKICAgIGluaXRpYWxfdmFsdWVzKDAsIDAsIE4tMSk7Cn0KCmludCBtYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKDApOwoKICAgIGludCBROwogICAgY2luID4+IE4gPj4gUTsKICAgIHNldHVwKE4pOwoKICAgIHdoaWxlIChRLS0pIHsKICAgICAgICBpbnQgQSwgQjsKICAgICAgICBjaW4gPj4gQSA+PiBCOwoKICAgICAgICB2aSBmcmVxKE5fS0VZUywgMCk7CiAgICAgICAgdmkgbm9kZXM7CiAgICAgICAgZnJlcXVlbmN5KDAsIDAsIE4tMSwgQSwgQiwgZnJlcSwgMCwgbm9kZXMpOwoKICAgICAgICBpbnQgbW9zdF9mcmVxX25vdGUgPSBpbmRleF9tYXhfZWxlbWVudChmcmVxKTsKICAgICAgICBpZiAobW9zdF9mcmVxX25vdGUpIHVwZGF0ZShub2RlcywgbW9zdF9mcmVxX25vdGUpOwogICAgfQoKICAgIHByaW50X3NlcXVlbmNlKDAsIDAsIE4tMSwgMSk7CiAgICByZXR1cm4gMDsKfQo=