Трохи складніші запити

Limits: 2 sec., 256 MiB

Задано масив \(a\) із \(n\) натуральних чисел. Потрібно відповісти на \(m\) запитів, кожен з яких одного із двох типів:

1. знайти розмір найбільшого префіксу масиву, сума чисел в якому не перевищує \(x\),

2. додати натуральне число \(d\) до \(i\)-го елементу.

Input

У першому рядку задано два цілих числа \(n\) і \(m\) — розмір масиву та кількість запитів відповідно.

У другому рядку задано \(n\) цілих чисел \(a_i\) — елементи масиву.

У наступних \(m\) рядках задано запити, по одному у рядку, у такому форматі:

• 1 x — запит першого типу,

• 2 i d — запит другого типу.

Output

Для кожного запиту першого типу виведіть, в окремому рядку, розмір найбільшого префіксу, сума чисел на якому не перевищує \(x\).

Constraints

\(1 \le n, m \le 10^5\).

\(1 \le a_i, d \le 10^3\).

\(1 \le i \le n\).

\(1 \le x \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
8 3 1 4 2 1 7 3 5 2 1 15 2 4 4 1 13	5 4

Notes

Зауважте, що розмір префіксу може бути рівний 0.