Пригоди Незнайки та його друзів

Усі ми пам'ятаємо історію про те, як Незнайка зі своїми друзями літали на повітряній кулі подорожувати. Але не всі знають, що не усі чоловічки помістились у кулі, так як у неї була обмежена вантажопідйомність.

У цій задачі Вам необхідно взнати, скільки же чоловічків полетіло подорожувати. Відомо, що посадка у кулю не є оптимальною, а саме: чоловічки сідають у кулю у тій черзі, у якій вони стоять, як тільки комусь з них не вистачає місця, він і усі чоловічки, що залишились у черзі, повертаються і йдуть додому.

Вхідні дані

У першому рядку міститься кількість чоловічків $n(1\le n\le 10^6)$ у квітковому місті. У другому рядку вага кожного з чоловічків у тому порядку, у якому вони будуть сідати у кулю. Усі ваги натуральні числа і не перевищують $10^9$. Далі йде кількість запитів $m(1\le m\le 10^5)$. Кожен запит являє собою один рядок. Перше число $t$ у рядку — тип запросу.

• Якщо $t=1$, то далі йде ще одне число $v(1\le v\le 10^9)$ — вантажопідйомність повітряної кулі.

• Якщо $t=2$, то далі йдуть два числа $x(1\le x\le n)$ та $y(1\le y\le 10^9)$ — вага чоловічка на позиції $x$ стає рівною $y$.

Вихідні дані

Для кожного запиту під номером один виведіть в окремому рядку кількість чоловічків, які помістились у кулю.

Приклади