원형 무대의 조명 점검

문제

공연장의 원형 무대 둘레에는 조명이 가리킬 수 있는 위치가 N개 있다. 위치에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있다. N번 위치에서 시계 방향으로 한 칸 더 이동하면 1번 위치가 되고, 1번 위치에서 반시계 방향으로 한 칸 이동하면 N번 위치가 된다. N이 1이면 어느 방향으로 이동하더라도 유일한 위치인 1번을 가리킨다. 공연을 시작하기 전, 담당자는 회전 조명에 Q개의 이동 명령을 순서대로 보낸다. 첫 번째 명령을 실행하기 전 조명은 1번 위치를 가리킨다. 각 명령은 정수 K_i 하나로 주어진다. K_i가 양수이면 현재 위치에서 시계 방향으로 K_i칸 이동한다. K_i가 음수이면 현재 위치에서 반시계 방향으로 절댓값이 |K_i|인 만큼 이동한다. K_i가 0이면 현재 위치를 그대로 유지한다. 한 명령의 이동 거리는 위치의 개수보다 클 수 있다. 이때 조명은 무대 둘레를 여러 바퀴 돌아서 이동하며, 명령을 실행하는 도중에 지나친 위치에서는 멈추지 않는다. 다음 명령은 바로 앞 명령의 이동이 끝난 위치에서 시작한다. 명령 사이에 조명을 처음 위치로 되돌리는 동작은 없다. 담당자는 각 명령을 모두 실행한 직후에만 점검표를 작성한다. 그때 조명이 1번 위치를 가리키고 있으면 점검표에 표시를 하나 남긴다. 명령 실행 중에 1번 위치를 지나친 것은 표시하지 않으며, 첫 번째 명령을 실행하기 전의 초기 위치도 표시 횟수에 포함하지 않는다. 이동하지 않는 명령도 실행 직후의 위치에 따라 표시할 수 있다. 모든 명령이 끝난 뒤 조명이 가리키는 위치와 점검표의 표시 횟수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ Q ≤ 1,000이다.
둘째 줄에 이동 명령을 나타내는 정수 K_1, K_2, …, K_Q가 공백으로 구분되어 주어진다. 모든 i에 대해 -1,000 ≤ K_i ≤ 1,000이다.

출력

모든 명령을 실행한 뒤 조명이 가리키는 위치의 번호와 점검표의 표시 횟수를 순서대로 공백으로 구분하여 한 줄에 출력한다. 표시가 한 번도 없으면 표시 횟수로 0을 출력한다.

6 5
2 4 -1 1 0

1 3

5 3
-1 -7 1

4 0

1 3
1000 -3 0

1 3

출처: Devin.KR 자체 제작