은하계 화음
시간 제한1초메모리 제한1024 MB
0에서 8까지의 음이 적힌 N개의 건반 배열에서 각 코드 [a,b]마다 구간 내 최빈 음(동률이면 가장 큰 음)을 찾아 구간의 모든 음에 그 값을 9로 나눈 나머지로 더한 뒤, 모든 코드를 처리한 후의 건반 상태를 출력한다.
문제
은하계 피아노 소나타 작곡 대회는 지능이 뛰어난 존재가 점점 더 많이 참가하면서 경연 난도를 계속 올리고 있다.
은하계 피아노에는 건반이 개 있고, 번호는 번부터 번까지다. 은하계 음 체계의 음은 부터 까지 아홉 개다. 처음에는 모든 건반이 음 에 대응한다.
참가자는 화음을 순서대로 연주한다. 화음 하나는 서로 다른 두 건반 와 로 이루어지고, 을 만족한다. 화음을 연주하면 피아노는 구간 에 속한 건반의 음 가운데 가장 많이 나타나는 음 를 낸다. 가장 많이 나타나는 음이 둘 이상이면 그중 가장 큰 음을 낸다. 음을 낸 직후 피아노는 구간 에 속한 모든 건반의 음을 바꾼다. 인 건반 의 새 음은 직전의 음에 를 더한 값을 로 나눈 나머지다.
예를 들어 건반이 개인 피아노의 음이 어느 순간 다음과 같다고 하자.
여기서 화음 를 연주하면 가장 많이 나타나는 음은 이고, 연주한 뒤의 음은 다음과 같다.
화음 개가 순서대로 주어진다. 화음을 모두 연주한 뒤 각 건반에 대응하는 음을 출력하는 프로그램을 작성하라.
입력
첫째 줄에 건반의 개수 과 화음의 개수 가 공백으로 구분되어 주어진다. (, )
다음 개 줄에는 각각 화음 하나를 나타내는 두 정수 와 가 주어진다. () 화음은 주어진 순서대로 연주된다.
출력
화음을 모두 연주한 뒤 건반 번부터 번까지의 음을 한 줄에 하나씩 개 출력한다.