Intergalactic Chords

The intergalactic piano sonata composition marathon keeps raising the difficulty for its competitors, because more and more beings of superior intelligence enter it.

The piano has $N$ keys, numbered $0$ to $N-1$. The intergalactic tonal system has nine notes, valued $0$ to $8$. At the start every key is assigned the same note, $1$.

A competitor plays a sequence of chords. Each intergalactic chord is made of two distinct keys $a$ and $b$ with $0 \le a < b < N$. When the chord is played, the piano sounds $f$, the most frequent note among the keys in the interval $[a, b]$. If several notes tie for most frequent, the piano sounds the largest of them. Right after sounding the note, the piano changes the note assigned to every key in the interval $[a, b]$. The new note of key $k$, for $a \le k \le b$, is its previous note plus $f$, modulo $9$.

For example, suppose the notes of a piano with $N = 15$ keys are the following at some moment.

If the chord $[3, 9]$ is played, the most frequent note is $4$, and the notes after the chord are the following.

Given the sequence of $Q$ chords, print the note assigned to each key of the piano after every chord in the sequence has been played.

The first line contains two integers $N$ and $Q$ separated by a space, the number of keys of the intergalactic piano and the number of chords. ($2 \le N \le 100000$, $1 \le Q \le 100000$)

Each of the next $Q$ lines contains two integers $A$ and $B$, one chord. ($0 \le A < B < N$) The chords are played in the given order.

Print $N$ integers, one per line, the notes assigned to keys $0$ through $N-1$ after all chords have been played.