이어지는 재생 목록

문제

음악 스트리밍 앱에 곡 M개로 이루어진 재생 목록이 있다. 목록의 곡에는 위에서부터 1번부터 M번까지 번호가 붙어 있으며, 같은 곡이 중복으로 들어 있더라도 목록에서의 번호가 다르면 서로 다른 항목으로 다룬다. 앱을 처음 열었을 때에는 항상 1번 곡이 선택되어 있다. 사용자는 이 상태에서 이동 버튼을 여러 번 눌러 듣고 싶은 곡을 고른다. 앱이 남긴 버튼 기록에는 세 종류의 정수만 들어 있다. 기록이 1이면 다음 곡 버튼을 누른 것이므로 현재 번호보다 1 큰 번호의 곡으로 이동한다. 단, M번 곡에서 다음 곡 버튼을 누르면 목록의 처음인 1번 곡으로 이동한다. 기록이 -1이면 이전 곡 버튼을 누른 것이므로 현재 번호보다 1 작은 번호의 곡으로 이동한다. 단, 1번 곡에서 이전 곡 버튼을 누르면 목록의 마지막인 M번 곡으로 이동한다. 기록이 0이면 현재 곡을 처음부터 다시 듣는 버튼을 누른 것이다. 이 버튼은 곡 안의 재생 위치만 바꾸므로 선택된 곡의 번호는 변하지 않는다. 이전 곡 버튼도 현재 곡의 재생 시간과 관계없이 반드시 앞서 설명한 번호 이동을 수행한다. 재생 목록에 곡이 하나뿐이면 세 종류의 버튼 중 어느 것을 눌러도 선택된 곡은 1번이다. 버튼 기록은 입력에 주어진 순서대로 하나씩 처리한다. 앞선 버튼으로 선택된 곡을 기준으로 다음 버튼을 적용하며, 버튼 사이에 곡이 끝나서 자동으로 다음 곡으로 넘어가는 일은 없다. 또한 기록을 처리하는 동안 재생 목록의 순서와 곡 수는 바뀌지 않는다. 모든 기록은 정해진 세 종류 중 하나이므로 무시해야 하는 잘못된 기록은 없다. N개의 버튼 기록을 모두 처리한 직후에 선택되어 있는 곡의 번호를 구한다.

입력

첫째 줄에 곡 수 M과 버튼 기록 수 N이 공백으로 구분되어 주어진다. 둘째 줄에 버튼 기록 C_1, C_2, ..., C_N이 누른 순서대로 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ M ≤ 1,000, 1 ≤ N ≤ 1,000이다. 각 C_i는 -1, 0, 1 중 하나이다.

출력

모든 버튼 기록을 처리한 직후에 선택되어 있는 곡의 번호를 정수 하나로 출력한다. 답은 항상 1 이상 M 이하이다.

4 7
-1 1 1 0 1 1 -1

3

1 5
1 -1 0 -1 1

1

3 4
-1 -1 -1 -1

3

출처: Devin.KR 자체 제작