实验室中有n台服务器,每台服务器都可以执行任务。每个服务器都有一个唯一的 ID——从 1 到 n 的整数。
已知一天中将有 q 个任务出现,其中第 i 个任务由三个整数表示:ti - 任务出现的时刻(以秒为单位),ki - 执行该任务所需的服务器数量,di - 执行该任务所需的时间(以秒为单位)。所有的 ti 都是不同的。
要执行第 i 个任务,您需要在第二个 ti 中未占用的 ki 服务器。服务器开始执行任务后,每个服务器将在接下来的 di 秒内忙碌。因此,它们将在 ti, ti + 1, ..., ti + di - 1 秒内变得繁忙。为了执行任务,将从所有未占用的服务器中选择具有最小 id 的 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 行中打印将执行此任务的服务器 id 的总和。否则,打印-1。
示例
输入 #1
4 3 1 3 2 2 2 1 3 4 3
输出 #1
6 -1 10
输入 #2
3 2 3 2 3 5 1 2
输出 #2
3 3
输入 #3
8 6 1 3 20 4 2 1 6 5 5 10 1 1 15 3 6 21 8 8
输出 #3
6 9 30 -1 15 36
注意
在第二个 1 的第一个示例中,第一个任务将会出现,它将在 id 为 1、2 和 3(id 之和等于 6)的服务器上执行两秒。在第二个 2 中,第二个任务将会到来,它将被忽略,因为此时只有服务器 4 未被占用。在第二个3中,第三个任务将会到来。此时,id为1、2、3的服务器将再次空闲,因此第三个任务将在所有id为1、2、3、4的服务器上执行(id之和为10)。
在第二个 3 的第二个示例中,第一个任务将会出现,它将在 id 为 1 和 2(id 之和为 3)的服务器上执行三秒。在第二个 5 中,第二个任务将会到来,它将在服务器 3 上执行,因为前两个服务器将忙于执行第一个任务。