Những Bước Nhảy Thoát Mảng

Có $n$ ô được đánh số từ $1$ đến $n$. Ở ô $i$ có một số dương $a_i$. Nếu đang ở $i$, bạn nhảy tới $i+a_i$; quá trình dừng ngay khi vị trí mới lớn hơn $n$. Bạn phải xử lý các phép thay đổi một độ dài bước và các truy vấn về toàn bộ đường nhảy.

• $0$ $p$ $x$: gán $a_p=x$.
• $1$ $p$: bắt đầu ở $p$. In vị trí cuối cùng còn nằm trong mảng và số bước đã thực hiện, kể cả bước cuối làm chỉ số vượt $n$.

Input

• Dòng đầu chứa $n,m$. Dòng thứ hai chứa $n$ số $a_i$. Mỗi trong $m$ dòng sau mô tả một thao tác theo một trong hai dạng trên.

Output

• Với mỗi truy vấn loại $1$, in vị trí cuối cùng còn nằm trong mảng và tổng số bước nhảy đã thực hiện, kể cả bước đưa chỉ số ra ngoài.

Constraints

• $1\le n,m\le 10^5$.
• $1\le a_i,x\le n$.
• $1\le p\le n$.
• Mọi chỉ số được đánh số từ $1$.

Scoring

• Subtask $1$ ($50$ điểm): $n,m\le 2000$.
• Subtask $2$ ($50$ điểm): không có ràng buộc bổ sung.

Example

6 5
2 3 1 2 1 4
1 1
0 3 4
1 1
1 2
0 6 1

6 4
3 2
6 3