Кавасиро Нитори — талантливый инженер. Поэтому ее назначили ответственной по обслуживанию поездов.
Всего существуют \(n\) моделей поездов, и в депо, в котором работает Нитори, в любой момент времени будет не более одного поезда каждой модели. Изначально в депо нет поездов, и в каждый из следующих \(m\) дней либо один поезд будет добавлен в депо, либо один поезд будет убран из депо. Когда добавляется поезд \(i\)-й модели в день \(t\), он будет работать \(x_i\) дней (включая день \(t\)), затем будет на ремонте в течение \(y_i\) дней, затем опять работать \(x_i\) дней, и так далее до тех пор, пока его не уберут из депо.
Чтобы следить за обслуживанием было проще, Нитори просит вас посчитать для каждого из дней, сколько поездов будут на ремонте в этот день.
В день, когда поезд убирают, он не считается находящимся в ремонте.
Выходные данные
Выведите \(m\) строк, каждая \(i\)-я из которых содержит одно целое число, обозначающее количество поездов, находящихся на ремонте в \(i\)-й день.
Примечание
Рассмотрим первый пример.
Первый день: Нитори добавляет поезд модели \(3\). Работает только поезд модели \(3\), и ни один поезд не находится в ремонте.
Второй день: Нитори добавляет поезд модели \(1\), поезд модели \(1\) работает, а поезд модели \(3\) находится в ремонте.
Третий день: Нитори убирает поезд модели \(1\). Ситуация такая же, как и в первый день.
Четвертый день: Нитори убирает поезд модели \(3\). Нет ни одного поезда.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
10 15
12 10
1 1
1 3
1 1
2 1
2 3
|
0
1
0
0
|
|
2
|
5 4
1 1
10000000 100000000
998244353 1
2 1
1 2
1 5
2 5
1 5
1 1
|
0
0
0
1
|