문제
선우는 게임을 좋아하는데, 그 중 "점프"라는 게임 많이 한다. "점프" 게임의 규칙은 다음과 같다.
N개의 구멍이 한줄로 늘어져 있으며, 왼쪽 부터 오른쪽으로 각 구멍에 1번 부터 N번의 숫자가 붙어있다.
각 구멍에는 파워가 있으며( i번 구멍의 파워를 ai라 하자), 공을 i번 구멍에 넣으면 공은 i + ai번 구멍으로 이동하고, 이를 계속 반복하게 된다(구멍에 써있는 파워만큼 오른쪽으로 이동한다).
다시 말해서, 처음에 1번 구멍의 파워가 10 이고 1번 구멍에 공을 넣었을 경우, 1 + 10 = 11번 구멍으로 이동하게 된다.
그 다음, 11번 구멍의 파워가 12일 경우, 23번 구멍으로 이동을 하고, 이러한 과정을 반복한다.
만약 해당하는 숫자가 없을 경우, 공은 구멍이 놓여있는 줄을 빠져나가게 된다.
플레이어는 다음에서 설명하는 명령을 M번 수행하게 된다.
* a번 구멍의 파워를 b로 바꾼다.
* a번 구멍에 공을 넣고, 공이 구멍이 놓인 줄에서 빠져나올 때 까지 몇번의 구멍을 거치는지 헤아린다.
선우는 두번째 명령에 대해서 잘 헤아리지 못하기 때문에 이를 헤아릴 수 있는 프로그램을 짜도록 하자.
입력
입력의 첫번째 줄에는 줄에 있는 구멍의 개수 N 과 명령의 횟수 M (1≤N≤105, 1≤M≤105)이 입력된다.
두번째 줄에는 N개의 정수가 입력되며, 이는 1번 부터 N번까지의 초기에 설정된 구멍의 파워를 뜻한다. 구멍의 파워는 N 이하의 양의 정수이다.
그 다음 M개의 줄에는 다음과 같이 명령에 대한 입력이 들어온다.
* 0 a b
* 1 a
0 a b는 a번 구멍의 파워를 b로 조정한다는 것이며, a, b는 정수이며 N 이하의 양의 정수다.
1 a는 a번 구멍에 공을 넣는다는 것이다.
출력
'1 a'꼴의 명령에 대해 공이 줄을 빠져나올 때 까지 거치게 되는 마지막 구멍의 번호와 구멍을 거친 횟수를 명령의 순서대로 한줄에 하나씩 출력한다.
예제
8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2
8 7
8 5
7 3
로그인해야 코드를 작성할 수 있어요.