Có ~N~ chiếc hố được đánh số từ ~1~ đến ~N~. Chiếc hố thứ ~i~ có sức mạnh ~P_i~. Nếu ném một quả bóng vào hố thứ ~i~, nó sẽ lập tức nhảy sang hố thứ ~i + P_i~. Quả bóng tiếp tục nhảy theo đúng quy tắc này cho đến khi vị trí tiếp theo vượt quá ~N~ (tức là ~i + P_i > N~), khi đó quả bóng dừng lại tại hố cuối cùng nó chạm vào.

Trong quá trình vận hành, sức mạnh của một số hố có thể thay đổi. Bạn cần xử lý một dãy truy vấn gồm hai loại:

• ~0~ ~x~ ~y~: Gán lại sức mạnh của hố ~x~ thành ~y~.
• ~1~ ~x~: Nếu ném quả bóng vào hố ~x~, hãy cho biết quả bóng dừng ở hố nào và tổng số bước nhảy đã thực hiện.

Bài toán yêu cầu bạn mô phỏng/khái quát quá trình nhảy theo sức mạnh dưới các cập nhật động, đảm bảo thời gian chạy hiệu quả cho tới ~10^5~ truy vấn.

Yêu cầu

Viết chương trình đọc dữ liệu đầu vào, xử lý ~Q~ truy vấn như mô tả, và với mỗi truy vấn loại ~1~ hãy in ra hai số nguyên: chỉ số hố cuối cùng quả bóng dừng lại, và số bước nhảy đã thực hiện từ điểm xuất phát.

Dữ liệu

• Dòng ~1~: hai số nguyên ~N~, ~Q~ ~(1 \le N, Q \le 10^5)~.
• Dòng ~2~: ~N~ số nguyên ~P_1, P_2, \dots, P_N~ biểu diễn sức mạnh các hố ~(1 \le P_i \le N)~.
• Dòng ~3..Q+2~: mỗi dòng là một truy vấn.
  • Loại cập nhật: ~0~ ~x~ ~y~ ~(1 \le x, y \le N)~ — gán ~P_x \leftarrow y~.
  • Loại hỏi: ~1~ ~x~ ~(1 \le x \le N)~ — ném bóng tại hố ~x~.

Kết quả

• Với mỗi truy vấn loại ~1~, in ra trên một dòng hai số nguyên: 1) chỉ số hố cuối cùng quả bóng dừng lại, 2) tổng số bước nhảy đã thực hiện.

Ví dụ

Input

7 5
1 1 1 2 2 3 2
1 1 
0 1 3
1 1
0 3 5
1 2

Output

6 5
6 3
3 2

Giải thích

• Trước mọi cập nhật: ~P = [1,1,1,2,2,3,2]~.
  • Truy vấn ~1~ ~1~: đường đi ~1 \to 2 \to 3 \to 4 \to 6 \to 9~ (vượt ~N=7~) nên dừng ở hố ~6~, tổng ~5~ bước.
• Sau cập nhật ~0~ ~1~ ~3~: ~P_1 = 3~.
  • Truy vấn ~1~ ~1~: đường đi ~1 \to 4 \to 6 \to 9~, dừng ở hố ~6~, tổng ~3~ bước.
• Sau cập nhật ~0~ ~3~ ~5~: ~P_3 = 5~.
  • Truy vấn ~1~ ~2~: đường đi ~2 \to 3 \to 8~, dừng ở hố ~3~, tổng ~2~ bước.

Ví dụ bổ sung

Input

5 4
2 1 2 1 10
1 1
0 3 1
1 1
1 4

Output

5 2
5 3
5 1

Giải thích

• Ban đầu ~P=[2,1,2,1,10]~.
  • ~1~ ~1~: ~1 \to 3 \to 5 \to 15~ (vượt ~N=5~), dừng ở ~5~, ~2~ bước (bước cuối vượt biên không tính).
• Cập nhật ~0~ ~3~ ~1~: ~P=[2,1,1,1,10]~.
  • ~1~ ~1~: ~1 \to 3 \to 4 \to 5 \to 15~, dừng ở ~5~, ~3~ bước.
  • ~1~ ~4~: ~4 \to 5 \to 15~, dừng ở ~5~, ~1~ bước.

Chấm điểm

Bộ test gồm nhiều file, tổng ~100~ điểm:

• Subtask 1 (20 điểm): ~1 \le N, Q \le 2000~ — có thể mô phỏng tuyến tính.
• Subtask 2 (30 điểm): chỉ có truy vấn loại ~1~ (không cập nhật).
• Subtask 3 (50 điểm): ràng buộc đầy đủ ~(1 \le N, Q \le 10^5)~. Gợi ý dùng chia khối (sqrt-decomposition) hoặc nhảy theo khối để trả lời nhanh truy vấn loại ~1~ và cập nhật loại ~0~ trong ~\mathcal{O}(\sqrt{N})~.

Lưu ý triển khai (không bắt buộc):

• Với chiến lược chia khối cỡ ~B \approx \lfloor \sqrt{N} \rfloor~, lưu cho mỗi vị trí ~i~ hai thông tin: hố kế tiếp ngoài khối ~next_i~ và số bước tới đó ~cnt_i~. Khi cập nhật ~P_x~, chỉ cần tái xây khối chứa ~x~ (đi ngược từ cuối khối). Trả lời truy vấn ~1~ ~x~ bằng cách nhảy theo khối cộng dồn số bước cho đến khi vượt ~N~.
• Đảm bảo số bước đếm không tính bước vượt biên (bước khiến ~i + P_i > N~); hố cuối cùng là hố trước khi vượt biên.