Вам дан массив \(a_1, a_2, \ldots, a_n\) из целых чисел. Этот массив невозрастающий.
Рассмотрим \(n\) магазинов, расположенных в ряд. Магазины пронумерованы целыми числами от \(1\) до \(n\) слева направо. Цена еды в \(i\)-м магазине равна \(a_i\) монет.
Вы должны обработать \(q\) запросов двух видов:
- 1 x y: для всех магазинов \(1 \leq i \leq x\) присвоить \(a_{i} = max(a_{i}, y)\).
- 2 x y: рассмотрим голодного мужчину с \(y\) монетами. Он посещает все магазины с \(x\)-го магазина по \(n\)-й, и если он может купить еду в текущем магазине, он покупает одну порцию этой еды. Найдите, какое количество порций еды он купит. Мужчина может покупать еду в магазине \(i\), если у него есть хотя бы \(a_i\) монет. После покупки количество его монет уменьшается на \(a_i\).
Примечание
В первом запросе голодный мужчина купит еду во всех магазинах с \(3\)-го по \(10\)-й.
Во втором запросе голодный мужчина купит еду в магазинах \(4\), \(9\) и \(10\).
После третьего запроса массив \(a_1, a_2, \ldots, a_n\) цен не поменяется и останется \(\{10, 10, 10, 6, 6, 5, 5, 5, 3, 1\}\).
В четвертом запросе голодный мужчина купит еду в магазинах \(2\), \(3\), \(4\), \(5\), \(9\) и \(10\).
После пятого запроса массив \(a\) цен станет \(\{10, 10, 10, 7, 6, 5, 5, 5, 3, 1\}\).
В шестом запросе голодный мужчина купит еду в магазинах \(2\) и \(4\).