English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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_.
[samples]
## Note
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.
实验室中有 #cf_span[n] 台服务器，每台都可以执行任务。每台服务器有一个唯一编号 —— 从 #cf_span[1] 到 #cf_span[n] 的整数。
已知一天内将有 #cf_span[q] 个任务到达，第 #cf_span[i] 个任务由三个整数描述：#cf_span[ti] —— 任务到达的时刻（秒），#cf_span[ki] —— 执行该任务所需的服务器数量，以及 #cf_span[di] —— 执行该任务所需的时间（秒）。所有 #cf_span[ti] 互不相同。
要执行第 #cf_span[i] 个任务，你需要在第 #cf_span[ti] 秒时有 #cf_span[ki] 台空闲的服务器。当服务器开始执行任务后，它们将在接下来的 #cf_span[di] 秒内保持忙碌，即在秒数 #cf_span[ti, ti + 1, ..., ti + di - 1] 内处于忙碌状态。执行任务时，将从所有空闲服务器中选择编号最小的 #cf_span[ki] 台服务器。如果在第 #cf_span[ti] 秒时空闲服务器不足，则该任务被忽略。
编写一个程序，确定哪些任务会被执行，哪些会被忽略。
第一行包含两个正整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n ≤ 100], #cf_span[1 ≤ q ≤ 105]) —— 服务器数量和任务数量。
接下来的 #cf_span[q] 行，每行包含三个整数，第 #cf_span[i] 行包含整数 #cf_span[ti], #cf_span[ki] 和 #cf_span[di] (#cf_span[1 ≤ ti ≤ 106], #cf_span[1 ≤ ki ≤ n], #cf_span[1 ≤ di ≤ 1000]) —— 第 #cf_span[i] 个任务到达的时刻、所需服务器数量和执行所需时间。任务按时间顺序给出，且到达时刻互不相同。
请输出 #cf_span[q] 行。如果第 #cf_span[i] 个任务被服务器执行，请在第 #cf_span[i] 行输出执行该任务的服务器编号之和；否则，输出 _-1_。
在第一个示例中，第 #cf_span[1] 秒时第一个任务到达，它将在编号为 #cf_span[1]、#cf_span[2] 和 #cf_span[3] 的服务器上执行（编号之和为 #cf_span[6]），持续两秒。第 #cf_span[2] 秒时第二个任务到达，它将被忽略，因为此时仅有服务器 #cf_span[4] 空闲。第 #cf_span[3] 秒时第三个任务到达，此时编号为 #cf_span[1]、#cf_span[2] 和 #cf_span[3] 的服务器已再次空闲，因此第三个任务将在所有编号为 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[4] 的服务器上执行（编号之和为 #cf_span[10]）。
在第二个示例中，第 #cf_span[3] 秒时第一个任务到达，它将在编号为 #cf_span[1] 和 #cf_span[2] 的服务器上执行（编号之和为 #cf_span[3]），持续三秒。第 #cf_span[5] 秒时第二个任务到达，它将在服务器 #cf_span[3] 上执行，因为前两台服务器正忙于执行第一个任务。
## Input
第一行包含两个正整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n ≤ 100], #cf_span[1 ≤ q ≤ 105]) —— 服务器数量和任务数量。接下来的 #cf_span[q] 行，每行包含三个整数，第 #cf_span[i] 行包含整数 #cf_span[ti], #cf_span[ki] 和 #cf_span[di] (#cf_span[1 ≤ ti ≤ 106], #cf_span[1 ≤ ki ≤ n], #cf_span[1 ≤ di ≤ 1000]) —— 第 #cf_span[i] 个任务到达的时刻、所需服务器数量和执行所需时间。任务按时间顺序给出，且到达时刻互不相同。
## Output
请输出 #cf_span[q] 行。如果第 #cf_span[i] 个任务被服务器执行，请在第 #cf_span[i] 行输出执行该任务的服务器编号之和；否则，输出 _-1_。
[samples]
## Note
在第一个示例中，第 #cf_span[1] 秒时第一个任务到达，它将在编号为 #cf_span[1]、#cf_span[2] 和 #cf_span[3] 的服务器上执行（编号之和为 #cf_span[6]），持续两秒。第 #cf_span[2] 秒时第二个任务到达，它将被忽略，因为此时仅有服务器 #cf_span[4] 空闲。第 #cf_span[3] 秒时第三个任务到达，此时编号为 #cf_span[1]、#cf_span[2] 和 #cf_span[3] 的服务器已再次空闲，因此第三个任务将在所有编号为 #cf_span[1]、#cf_span[2]、#cf_span[3] 和 #cf_span[4] 的服务器上执行（编号之和为 #cf_span[10]）。
在第二个示例中，第 #cf_span[3] 秒时第一个任务到达，它将在编号为 #cf_span[1] 和 #cf_span[2] 的服务器上执行（编号之和为 #cf_span[3]），持续三秒。第 #cf_span[5] 秒时第二个任务到达，它将在服务器 #cf_span[3] 上执行，因为前两台服务器正忙于执行第一个任务。
Let $ n $ be the number of servers, indexed from $ 1 $ to $ n $.
Let $ q $ be the number of tasks.
Each task $ i $ (for $ i = 1, 2, \dots, q $) is characterized by a triplet $ (t_i, k_i, d_i) $, where:
- $ t_i \in \mathbb{Z}^+ $: the arrival time (in seconds),
- $ k_i \in \mathbb{Z}^+ $: the number of servers required,
- $ d_i \in \mathbb{Z}^+ $: the duration of the task (in seconds).
Define a set $ B \subseteq \{1, 2, \dots, n\} \times \mathbb{Z}^+ $ to represent busy servers:
Each element $ (s, e) \in B $ means server $ s $ is busy until (but not including) time $ e $.
At time $ t_i $, the set of available servers is:
$$
A_i = \left\{ s \in \{1, 2, \dots, n\} \mid \forall (s', e) \in B, \; s' = s \implies e \leq t_i \right\}
$$
Let $ A_i $ be sorted in increasing order.
If $ |A_i| \geq k_i $, then the task is assigned to the first $ k_i $ servers in $ A_i $:
$$
S_i = \{ a_1, a_2, \dots, a_{k_i} \}, \quad \text{where } a_1 < a_2 < \dots < a_{k_i} \text{ are the smallest } k_i \text{ servers in } A_i
$$
The sum of server IDs is:
$$
\text{sum}_i = \sum_{s \in S_i} s
$$
Then, update the busy set:
$$
B \leftarrow B \cup \{ (s, t_i + d_i) \mid s \in S_i \}
$$
Otherwise, if $ |A_i| < k_i $, the task is ignored, and $ \text{sum}_i = -1 $.
**Input:**
- $ n, q $
- Sequence of $ q $ tasks $ (t_i, k_i, d_i) $, with $ t_1 < t_2 < \dots < t_q $
**Output:**
For each task $ i $, output $ \text{sum}_i $ if assigned, else $ -1 $.
API Response (JSON)
{
"problem": {
"name": "C. Servers",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF747C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There are _n_ servers in a laboratory, each of them can perform tasks. Each server has a unique id — integer from 1 to _n_.\n\nIt is known that during the day _q_ tasks will come, the _i_\\-th of them is...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "实验室中有 #cf_span[n] 台服务器，每台都可以执行任务。每台服务器有一个唯一编号 —— 从 #cf_span[1] 到 #cf_span[n] 的整数。\n\n已知一天内将有 #cf_span[q] 个任务到达，第 #cf_span[i] 个任务由三个整数描述：#cf_span[ti] —— 任务到达的时刻（秒），#cf_span[ki] —— 执行该任务所需的服务器数量，以及 #cf_sp...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $ be the number of servers, indexed from $ 1 $ to $ n $. \nLet $ q $ be the number of tasks. \n\nEach task $ i $ (for $ i = 1, 2, \\dots, q $) is characterized by a triplet $ (t_i, k_i, d_i) $, ...",
"is_translate": false,
"language": "Formal"
}
]
}