CF747C.Servers

There are n servers in a laboratory, each of them can perform tasks. Each server has a unique id — integer from 1 to n.

It is known that during the day q tasks will come, the i-th of them is characterized with three integers: t__i — the moment in seconds in which the task will come, k__i — the number of servers needed to perform it, and d__i — the time needed to perform this task in seconds. All t__i are distinct.

To perform the i-th task you need k__i servers which are unoccupied in the second t__i. After the servers begin to perform the task, each of them will be busy over the next d__i seconds. Thus, they will be busy in seconds t__i, t__i + 1, ..., t__i + d__i - 1. For performing the task, k__i servers with the smallest ids will be chosen from all the unoccupied servers. If in the second t__i there are not enough unoccupied servers, the task is ignored.

Write the program that determines which tasks will be performed and which will be ignored.

实验室中有 $n$ 台服务器，每台服务器均可执行任务。每台服务器具有唯一的编号——一个从 $1$ 到 $n$ 的整数。

已知当天将有 $q$ 个任务到达，其中第 $i$ 个任务由三个整数刻画：$t_i$ —— 该任务到达的时刻（单位：秒），$k_i$ —— 执行该任务所需的服务器数量，以及 $d_i$ —— 执行该任务所需的时间（单位：秒）。所有 $t_i$ 均互不相同。

要执行第 $i$ 个任务，需在第 $t_i$ 秒时选择 $k_i$ 台空闲的服务器。服务器一旦开始执行该任务，将在接下来的 $d_i$ 秒内持续处于忙碌状态。因此，这些服务器将在第 $t_i,\,t_i+1,\,\dots,\,t_i+d_i-1$ 秒内保持忙碌。执行该任务时，将从所有空闲服务器中选取编号最小的 $k_i$ 台服务器。若在第 $t_i$ 秒时空闲服务器的数量不足 $k_i$ 台，则该任务被忽略。

请编写程序，判断哪些任务将被执行，哪些任务将被忽略。

The first line contains two positive integers n and q (1 ≤ n ≤ 100, 1 ≤ q ≤ 105) — the number of servers and the number of tasks.

Next q lines contains three integers each, the i-th line contains integers t__i, k__i and d__i (1 ≤ t__i ≤ 106, 1 ≤ k__i ≤ n, 1 ≤ d__i ≤ 1000) — the moment in seconds in which the i-th task will come, the number of servers needed to perform it, and the time needed to perform this task in seconds. The tasks are given in a chronological order and they will come in distinct seconds.

第一行包含两个正整数 $n$ 和 $q$（$1 ≤ n ≤ 100$，$1 ≤ q ≤ 10^5$）—— 分别表示服务器的数量和任务的数量。

接下来的 $q$ 行每行包含三个整数，其中第 $i$ 行包含整数 $t_i$、$k_i$ 和 $d_i$（$1 ≤ t_i ≤ 10^6$，$1 ≤ k_i ≤ n$，$1 ≤ d_i ≤ 1000$）—— 分别表示第 $i$ 个任务到达的时刻（单位：秒）、执行该任务所需的服务器数量，以及执行该任务所需的时间（单位：秒）。任务按时间顺序给出，且所有任务的到达时刻互不相同。

Print q lines. If the i-th task will be performed by the servers, print in the i-th line the sum of servers' ids on which this task will be performed. Otherwise, print -1.

输出 q 行。如果第 i 个任务将由服务器执行，则在第 i 行输出执行该任务的所有服务器的编号之和；否则，输出 -1。

In the first example in the second 1 the first task will come, it will be performed on the servers with ids 1, 2 and 3 (the sum of the ids equals 6) during two seconds. In the second 2 the second task will come, it will be ignored, because only the server 4 will be unoccupied at that second. In the second 3 the third task will come. By this time, servers with the ids 1, 2 and 3 will be unoccupied again, so the third task will be done on all the servers with the ids 1, 2, 3 and 4 (the sum of the ids is 10).

In the second example in the second 3 the first task will come, it will be performed on the servers with ids 1 and 2 (the sum of the ids is 3) during three seconds. In the second 5 the second task will come, it will be performed on the server 3, because the first two servers will be busy performing the first task.

在第一个样例中，第 2 秒时第一个任务到达，它将在编号为 1、2 和 3 的服务器上执行（编号之和为 6），持续 2 秒。第 4 秒时第二个任务到达，该任务将被忽略，因为此时仅有编号为 4 的服务器空闲。第 6 秒时第三个任务到达。此时编号为 1、2 和 3 的服务器已再次空闲，因此第三个任务将在编号为 1、2、3 和 4 的所有服务器上执行（编号之和为 10）。

在第二个样例中，第 3 秒时第一个任务到达，它将在编号为 1 和 2 的服务器上执行（编号之和为 3），持续 3 秒。第 5 秒时第二个任务到达，它将在编号为 3 的服务器上执行，因为前两台服务器正忙于执行第一个任务。