은하계 화음

은하계 피아노 소나타 작곡 대회는 지능이 뛰어난 존재가 점점 더 많이 참가하면서 경연 난도를 계속 올리고 있다.

은하계 피아노에는 건반이 $N$개 있고, 번호는 $0$번부터 $N-1$번까지다. 은하계 음 체계의 음은 $0$부터 $8$까지 아홉 개다. 처음에는 모든 건반이 음 $1$에 대응한다.

참가자는 화음을 순서대로 연주한다. 화음 하나는 서로 다른 두 건반 $a$와 $b$로 이루어지고, $0 \le a < b < N$을 만족한다. 화음을 연주하면 피아노는 구간 $[a, b]$에 속한 건반의 음 가운데 가장 많이 나타나는 음 $f$를 낸다. 가장 많이 나타나는 음이 둘 이상이면 그중 가장 큰 음을 낸다. 음을 낸 직후 피아노는 구간 $[a, b]$에 속한 모든 건반의 음을 바꾼다. $a \le k \le b$인 건반 $k$의 새 음은 직전의 음에 $f$를 더한 값을 $9$로 나눈 나머지다.

예를 들어 건반이 $N = 15$개인 피아노의 음이 어느 순간 다음과 같다고 하자.

여기서 화음 $[3, 9]$를 연주하면 가장 많이 나타나는 음은 $4$이고, 연주한 뒤의 음은 다음과 같다.

화음 $Q$개가 순서대로 주어진다. 화음을 모두 연주한 뒤 각 건반에 대응하는 음을 출력하는 프로그램을 작성하라.

첫째 줄에 건반의 개수 $N$과 화음의 개수 $Q$가 공백으로 구분되어 주어진다. ($2 \le N \le 100000$, $1 \le Q \le 100000$)

다음 $Q$개 줄에는 각각 화음 하나를 나타내는 두 정수 $A$와 $B$가 주어진다. ($0 \le A < B < N$) 화음은 주어진 순서대로 연주된다.

화음을 모두 연주한 뒤 건반 $0$번부터 $N-1$번까지의 음을 한 줄에 하나씩 $N$개 출력한다.