Боб играет в игру «Космический Солитер». Цель этой игры — построить космический корабль, но для ее достижения требуется сначала собрать достаточное количество ресурсов \(n\) типов, пронумерованных от \(1\) до \(n\). Боб должен собрать не менее \(a_i\) единиц \(i\)-го ресурса. Для удобства назовем \(a_i\) целью для ресурса \(i\).
Для производства одной единицы любого ресурса нужно потратить \(1\) ход (и каждый ход можно производить только один ресурс). Однако для ускорения игры в ней введена система достижений. Каждое достижение описывается тройкой \((s_j, t_j, u_j)\) и обозначает следующее: как только Боб соберет \(t_j\) единиц ресурса \(s_j\), он сразу же получит дополнительную единицу ресурса \(u_j\), не тратя ход на ее производство. Возможно, награда за достижение позволит активировать другое достижение — таким образом за один ход можно набрать большое количество разных ресурсов.
Система достижений устроена таким образом, что не существует двух достижений, у которых одновременно одинаковые \(s_j\) и \(t_j\). То есть за достижение \(t_j\) единиц ресурса \(s_j\) нельзя получить в награду более одного ресурса.
Ни один бонусный ресурс не дается за достижение \(0\) единиц какого-либо ресурса. Также не существует достижений, для которых надо собрать \(a_i\) или более соответствующего ресурса. Формально, \(0 < t_j < a_{s_j}\).
Могут существовать достижения, для которых тип требуемого ресурса совпадает с типом бонусного ресурса, то есть \(s_j = u_j\).
Изначально в игре нет достижений. Вам нужно обработать \(q\) обновлений игры, каждое из которых добавляет, удаляет или меняет какое-то достижение. После каждого обновления посчитайте минимальное количество ходов, требуемое для завершения игры (то есть для того, чтобы собрать не менее \(a_i\) единиц \(i\)-го ресурса для всех \(i \in [1, n]\)).
Выходные данные
Выведите \(q\) строк, в \(i\)-й из которых должно быть одно целое число — ответ на задачу после \(i\)-го обновления.
Примечание
После первого обновления оптимальная стратегия — следующая: произвести ресурс \(2\) и получить бесплатно ресурс \(1\). Затем произвести ресурс \(2\) дважды и \(1\) один раз, и мы завершим игру за четыре хода.
После второго обновления оптимальная стратегия состоит в том, чтобы произвести ресурс \(2\) три раза — в первые два хода мы дополнительно получим по единице ресурса \(1\).
После третьего обновления оптимальная стратегия — следующая:
- Сначала произвести единицу ресурса \(2\) и получить бесплатную единицу \(1\). После этого мы получим еще одну бесплатную единицу \(1\). Количество ресурсов: \([2, 1]\).
- После этого произвести единицу ресурса \(2\) и получить еще одну бесплатную единицу \(1\).
- Опять произвести единицу ресурса \(2\).
Количество ресурсов в конце игры: \([3, 3]\). Для достижения цели нам потребовалось три хода. Обратите внимание, что у нас есть лишняя единица ресурса \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 3
5
2 1 1
2 2 1
1 1 1
2 1 2
2 2 0
|
4
3
3
2
3
|