1004. 坪厕鸡

题目描述

你是 HDU ACM 集训队队长。今天，海豚教练交给你一项艰巨的任务：负责本次 HDU 多校比赛。本场比赛共有 n 支队伍参与，系统后端配备了 k 台完全相同的评测机。比赛期间系统共接受到了 m 次提交，第 i 次提交由队伍 ai 在第

bi 秒发起，需要消耗 ci 秒进行评测。保证所有的 bi 严格单调递增。

为了避免队伍在短时间内连续大量提交代码，从而占用过多评测资源。你决定采用如下的调度策略：

• 每台评测机同一时刻只能评测一份提交。对于任意队伍，同一时刻至多只能有一份提交处于评测状态。

• 每次提交到达后，将会进入等待队列。

• 每当存在空闲评测机时，系统会在等待队列中，筛选出所有满足

“所属队伍当前无正在评测提交”的提交。若存在这样的提交，则选择其中提交时间 bi 最早的一份开始评测。

• 系统将会不断重复上述调度过程，直到不存在空闲评测机，或不存在符合条件的等待提交为止。

若第 i 次提交从第 T 秒开始评测，则它将会连续占用一台评测机 ci

秒，评测过程不可中断。该提交在第 T + ci 秒结束评测，此时该评测

机立即变为空闲，同时该提交所属队伍也立即恢复空闲状态，并可能触发新的调度。特别地，若同一时刻既有新的提交到达，又有若干评测结束，则这些事件均视为已发生后，系统再进行调度。作为 HDU ACM 集训队队长，你想推演出整个系统的评测过程，请你求出这 m 次提交实际开始被评测的时间。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 103 )，表示数据组数。对于每组测试数据：第一行包含三个正整数 n, m, k (1 ≤ n, m, k ≤ 2 × 105 )，分别代表队伍总数、提交总数以及评测机总数。接下来的 m 行，每行三个正整数 ai, bi, ci (1 ≤ ai ≤ n, 1 ≤ bi, ci ≤

109 )，分别代表第 i 次提交的所属队伍编号，提交时间（秒）以及所需评测时间（秒）。保证所有的 bi 严格单调递增，即 b1 < b2 <⋯ < bm。

保证所有测试数据中 n 之和与 m 之和均不超过 2 × 105。

输出格式

对于每组测试数据：输出一行 m 个整数，第 i 个整数表示第 i 次提交实际开始被评测的时间。

样例输入

2
4 6 3
1 1 10
2 2 5
1 5 1
3 6 15
4 10 15
2 11 1
10 12 4
1 1 8
2 2 4
1 3 3
3 4 10
4 5 2
5 6 5
2 7 6
6 8 1
1 9 2
7 10 4
3 11 3
8 12 2

样例输出

1 2 11 6 10 12
1 2 9 4 5 6 7 11 12 12 14 13

提示

在第一组样例中：第 1 秒，队伍 1 提交了编号为 1 的提交，提交顺利进入评测。当前正在评测的提交编号为 [1]。第 2 秒，队伍 2 提交了编号为 2 的提交，提交顺利进入评测。当前正在评测的提交编号为 [1, 2]。第 5 秒，队伍 1 提交了编号为 3 的提交，但此时队伍 1 编号为 1 的提交还未评测完成，故这次提交未进入评测，进入等待队列。当前正在评测的提交编号为 [1, 2]。第 6 秒，队伍 3 提交了编号为 4 的提交，提交顺利进入评测。当前正在评测的提交编号为 [1, 2, 4]。第 7 秒，队伍 2 编号为 2 的提交评测结束，此时等待队列中只有队伍

1 编号为 3 的提交，但队伍 1 编号为 1 的提交仍未评测完毕，故没有新的提交能进入评测。当前正在评测的提交编号为 [1, 4]。第 10 秒，队伍 4 提交了编号为 5 的提交，提交顺利进入评测。当前正在评测的提交编号为 [1, 4, 5]。第 11 秒，队伍 1 编号为 1 的提交评测结束，同时队伍 2 提交了编号为 6 的提交，但是提交时间晚于队伍 1 编号为 3 的提交，故编号为 3的提交进入评测。当前正在评测的提交编号为 [3, 4, 5]。

第 12 秒，队伍 1 编号为 3 的提交评测结束，等待队列中的队伍 2 编号为 6 的提交顺利进入评测。当前正在评测的提交编号为 [4, 5, 6]。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）