Có \(n\) cái lỗ nằm dọc theo một đường thẳng đánh số \(1, 2, ..., n\) từ trái qua phải. Trong lỗi thứ \(i\) có đặt một lò xo có độ đàn hồi \(a_i\). Nếu như có một viên bi rơi vào lỗ \(i\) thì nó sẽ nảy lên rơi vào lỗ \(i + a_i\) nếu như \(i + a_i \le n\) còn nếu không sẽ ra khỏi hàng (nhảy vượt qua lỗ \(n\)), quá trình này lại tiếp tục như vậy... cho đến khi viên bi nhảy vượt qua lỗ \(n\). Có \(m\) thao tác được người chơi bi thực hiện lần lượt thuộc một trong hai loại sau:

• Thay lò xo có độ đàn hồi \(b\) vào lỗ \(a\)
• Bắn một viên bi vào lỗ \(a\) và đếm xem nó nhảy qua bao nhiêu lỗ trước khi vượt qua lỗ \(n\) ?.
  In ra giá trị này.

Yêu cầu: Viết chương trình thực hiện \(m\) thao tác nói trên

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m (1 \le n, m \le 105 )\)

• Dòng thứ hai chứa n số nguyên dương không vượt quá n là độ đàn hồi ban đầu của các
  lò xo đặt ở các lỗ \(1, 2, ..., n\)

• m dòng cuối, mỗi dòng mô tả một thao tác thuộc một trong hai dạng:

• \(0\) \(a\) \(b\): Đặt lại độ đàn hồi của lò xo ở lỗ \(a\) thành \(b\) \((1 \le a, b \le n)\)

• \(1\) \(a\): Tính số lỗ mà viên bi nhảy vào nếu bắn vào lỗ \(a\) \((1 \le a \le n)\)

Output

• Với các thao tác dạng \(1\) \(a\) in ra trên một dòng hai số nguyên, số thứ nhất là số hiệu của lỗ cuối cùng trong hàng mà viên bi nhảy đến, số thứ hai là số lỗ mà viên bi nhảy vào trước khi vượt qua lỗ \(n\)

Example

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