Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.
В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.
В первой строке содержится количество человечков в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают . Далее следует количество запросов . Каждый запрос представляет собой одну строку. Первое число в строке — тип запроса.
Если , то далее следует еще одно число — грузоподъемность воздушного шара.
Если , то далее следует два числа и — вес человечка на позиции становится равным .
Для каждого запроса с номером выведите в отдельной строке количество человечков, поместившихся в шар.