Sau nhiều ngày online LQDOJ liên tục, uia quyết định off một thời gian để nghỉ ngơi.

Trước khi offline, uia lập một danh sách gồm \(N\) hoạt động muốn làm trong kỳ nghỉ. Các hoạt động được đánh số từ \(1\) đến \(N\) theo đúng thứ tự dự định thực hiện.

Hoạt động thứ \(i\) cần \(a_i\) đơn vị thời gian.

Mỗi ngày, uia chỉ chọn một đoạn các hoạt động liên tiếp để thực hiện. Nếu chọn các hoạt động từ vị trí \(L\) đến vị trí \(R\), tổng thời gian cần dùng là:

Tuy nhiên, kế hoạch nghỉ ngơi của uia có thể thay đổi theo thời gian. Có \(Q\) sự kiện thuộc một trong hai loại:

• 1 p x: thay đổi thời gian cần để thực hiện hoạt động thứ \(p\) thành \(x\).
• 2 t: hỏi số lượng hoạt động liên tiếp nhiều nhất mà uia có thể thực hiện sao cho tổng thời gian không vượt quá \(t\).

uia không bắt buộc phải bắt đầu từ hoạt động đầu tiên trong danh sách.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 7000\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một sự kiện theo một trong hai dạng:
  • 1 p x (\(1 \le p \le N, 1 \le x \le 10^9\)).
  • 2 t (\(1 \le t \le 10^{18}\)).

Output

• Với mỗi sự kiện loại 2, in ra một dòng là số lượng hoạt động liên tiếp nhiều nhất mà uia có thể thực hiện.

Example

5 6
4 2 3 1 5
2 7
2 10
1 3 10
2 10
1 5 1
2 10

3
4
2
2