Ивар Бескостный — великий лидер. Он пытается захватить Каттегат, в данный момент находящийся под контролем Лагерты. Битва началась, и волны воинов Ивара гибнут одна за другой.
У Ивара \(n\) воинов, он выставляет их вдоль прямой напротив главных ворот так, что \(i\)-й воин стоит сразу за \((i-1)\)-м воином. Первый воин возглавляет атаку.
Каждый атакующий воин может выдержать до \(a_i\) стрел, прежде чем он падёт, где \(a_i\) — сила \(i\)-го воина.
Лагерта приказывает своим воинам выпустить \(k_i\) стрел в течение \(i\)-й минуты, стрелы одна за одной поражают первого всё ещё стоящего воина. После того, как все воины Ивара падут и стрелы, находящиеся в воздухе в данный момент, пролетят, Тор бьёт по земле своим молотом и все воины Ивара получают свои силы назад и возвращаются в битву. Другими словами, если все воины умрут в минуту \(t\), в конце этой минуты \(t\) они все встанут и будут сражаться.
Битва будет идти \(q\) минут. После каждой минуты вы должны сообщить Ивару, сколько из его воинов находится в строю.
Выходные данные
Выведите \(q\) строк, \(i\)-я из которых содержит число воинов Ивара, находящихся в строю после \(i\)-й минуты.