Giả sử Gấu có một dãy số ~A = \{A_1, A_2, \dots, A_N\}~, Gấu sẽ tạo ra dãy ~B~ gồm ~2^N~ phần tử bằng cách tính tổng các dãy con (không nhất thiết liên tiếp của ~A~) và thêm tổng đó vào dãy ~B~. Gấu định nghĩa MEX dãy số ~A~ hay ~f(A)~ chính là số nguyên nhỏ nhất không xuất hiện trong dãy ~B~. Dãy rỗng cũng được Gấu coi là dãy con của ~A~.

Khi đã biết được ~f(A)~, Gấu thực hiện thao tác sau nhiều lần:

• Nếu ~f(A) > A_1 + A_2 + \dots + A_N~ thì dừng lại.
• Thêm một phần tử mang giá trị ~X~ vào dãy (lúc này ~N = N + 1, A_N = X~).

Gọi số thao tác ít nhất Gấu đã thực hiện cho đến khi dừng lại là ~g(A)~.

Ví dụ Gấu đang có dãy ~A = \{1, 2, 5\}~, thì các thao tác Gấu sẽ thực hiện như sau:

• Tạo dãy ~B = \{0, 1, 2, 3, 5, 6, 7, 8\}~, tính ~f(A) = 4 < A_1 + A_2 + A_3 = 1 + 2 + 5 = 9~.
• Gấu thêm phần tử mang giá trị ~4~ vào, lúc này dãy là ~A = \{1, 2, 5, 4\}~.
• Tạo dãy ~B = \{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 9, 10, 11, 12\}~, tính ~f(A) = 13 > A_1 + A_2 + A_3 + A_4 = 1 + 2 + 5 + 4 = 12~.

Gấu dừng thao tác lại, lúc này ~g(A) = 1~.

Quay về thực tế, Gấu đang có một dãy số ~A~ gồm ~N~ phần tử và quyết định thực hiện ~Q~ thao tác trên dãy số này. ~Q~ thao tác sẽ thuộc một trong hai loại:

• ~1~ ~X~ ~Y~: Đặt ~A_X = Y~.
• ~2~ ~L~ ~R~: Tính ~g(A[L...R])~.

Hãy giúp Gấu tìm đáp án cho mỗi truy vấn loại hai nhé.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \leq N, Q \leq 2*10^5)~.
• Dòng hai chứa ~N~ số nguyên mô tả dãy ~A~ ~(1 \leq A_i \leq 10^{18})~.
• ~Q~ dòng sau, mỗi dòng chứa các truy vấn thuộc hai loại:
  • ~1~ ~X~ ~Y~ ~(1 \leq X \leq N, 1 \leq Y \leq 10^{18})~
  • ~2~ ~L~ ~R~ ~(1 \leq L \leq R \leq N)~.

Dữ liệu ra

Với mỗi truy vấn loại hai, hãy in ra đáp án trên một dòng.

Ví dụ

Input

4 4
1 2 5 2
2 1 3
1 2 3
2 1 4
2 2 4

Output

1
0
1

Tính điểm

• Subtask 1 (10 điểm): ~N \leq 4, Q \leq 2~.
• Subtask 2 (20 điểm): ~Q = 1~.
• Subtask 3 (30 điểm): ~Q \leq 2709~.
• Subtask 4 (40 điểm): Không có ràng buộc gì thêm.