C. Серверы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В лаборатории есть n серверов, каждый из которых может выполнять задания. Серверы пронумерованы уникальными целыми числоми от 1 до n.

Известно, что в течение суток поступит q заданий, i-е из которых характеризуется тремя величинами: ti — секунда поступления задания, ki — количество серверов, которые нужны для его выполнения, а также di — продолжительность выполнения этого задания в секундах. Все ti — различны.

Для того, чтобы выполнить i-е пришедшее задание, нужно ki серверов, которые должны быть свободны в секунду ti. После начала выполнения задания каждый из них будет занят в течение ближайших di секунд. Таким образом, они будут заняты в секунды ti, ti + 1, ..., ti + di - 1. Из всех свободных серверов для выполнения будут выбраны ki серверов с наименьшими номерами. Если в секунду ti не хватает свободных серверов, то задание будет проигнорировано.

Напишите программу, определяющую, какие задания будут выполнены серверами, а какие будут проигнорированы.

Входные данные

В первой строке следует два целых положительных числа n и q (1 ≤ n ≤ 100, 1 ≤ q ≤ 105) — количество серверов и количество заданий.

В каждой из следующих q строк записаны по три целых числа, в i-й из них записаны целые числа ti, ki и di (1 ≤ ti ≤ 106, 1 ≤ ki ≤ n, 1 ≤ di ≤ 1000) — секунда поступления i-го задания, количество серверов, необходимых для его выполнения, а также время выполнения этого задания. Задания заданы в хронологическом порядке, и все они поступят в разные секунды.

Выходные данные

Выведите q строк. Если i-е задание будет принято на выполнение, выведите в i-й строке сумму номеров серверов, на которых будет выполняться это задание. В противном случае выведите -1.

Примеры
Входные данные
4 3
1 3 2
2 2 1
3 4 3
Выходные данные
6
-1
10
Входные данные
3 2
3 2 3
5 1 2
Выходные данные
3
3
Входные данные
8 6
1 3 20
4 2 1
6 5 5
10 1 1
15 3 6
21 8 8
Выходные данные
6
9
30
-1
15
36
Примечание

В первом примере в секунду 1 придет первое задание, которое будет выполняться на серверах с номерами 1, 2 и 3 (сумма номеров равна 6) в течение двух секунд. В секунду 2 поступит второе задание, которое будет проигнорировано, так как в эту секунду будет свободен только сервер номер 4. В секунду 3 придет третье задание. К этому времени как раз освободятся серверы с номерами 1, 2 и 3, поэтому третье задание будет выполняться на всех имеющихся серверах с номерами 1, 2, 3 и 4 (сумма номеров равна 10).

В втором примере в секунду 3 придет первое задание, которое будет выполняться на серверах с номерами 1 и 2 (сумма равна 3) в течение трех секунд. В секунду 5 поступит второе задание, которое будет выполняться на сервере номер 3, так как первые два сервера будут заняты выполнением первого задания.