题目解析

在无线用户管理系统中，一个用户的呼叫流程称为一个 task，由多个子流程 (Procedure) 组成。每个 Procedure 可以嵌套调用其他 Procedure，甚至可以递归调用自身。为了优化系统性能，需要计算每个 Procedure 的实际执行时间，即不包括子 Procedure 执行时间的部分。如果一个 Procedure 被多次调用，应输出其最长的执行时间。

问题要点

1. 嵌套调用与递归调用：需要使用栈来模拟 Procedure 的调用和返回过程。
2. 多次调用：同一个 Procedure 可能被多次调用，每次调用的执行时间可能不同，需记录每次调用的执行时间，并取最大值。
3. 时间戳处理：日志中的时间戳是严格递增的，且每个 Procedure 的执行时间至少为1。

题目内容

无线用户管理系统中，一个用户呼叫流程称为一个 $task$ ，$task$ 由若干个子流程($Procedure$)组成，$Procedure$ 可以继续调用更小粒度的 $Procedure$ ; $task$ 是呼叫流程的入口，也是一种特殊的Procedure。

为了对呼叫流程处理性能进行优化分析，调度框架在每个 $Procedure$ 的入口和出口记录了系统时间戳的日志。现在需要你根据日志信息分析得到每个 $Procedure$ 的实际执行时间(不包括子 $procedure$ 的执行时间)。

备注:

1. $Procedure$可以被调用多次，也可以被递归调用;

2. $Procedure$ 的入口记录表示 $Procedure$ 从记录时间戳的起始开始执行出口记录表示 $Procedure$ 在记录时间截的末尾结束执行;

3. $Procedure$ 的日志时间截至少间隔1

4. 如果同一个 $procedure$ 多次调用且执行时间不相同，请输出最长的执行时间。

输入描述

第一行输入 $Procedure$ 的个数 $m$ 和日志记录个数，以空格隔开。$m$ 取值范围 $[1,100]$，$n$ 取值范围 $[2,500]$ ;

后面的 $n$ 行输入日志记录，每条日志由 $3$ 个整数组成并以空格隔开。日志格式: $Procedure$ 编号(取值范围:$[0,m)$),日志类型(入口: $0$，出口: $1$ )，时间戳(取值范围:$[0,1000000000]$)

输出描述

以 $Procedure$ 编号顺序输出每个 $Procedure$ 的实际执行时间(不包括子 $procedure$ 的执行时间)，以空格隔开;

样例1

输入

2 6
0 0 0
1 0 2
1 1 5
1 0 6
1 1 9
0 1 10

输出

3 4

说明

如上图:

$Procedure0$ 在时间戳 $0$ 的开始执行，执行 $2$ 个单位时间，于时间戳 $1$ 的未尾结束执行。

$Procedure1$ 在时间戳 $2$ 的开始执行，执行 $4$ 个单位时间，于时间戳 $5$ 的末尾结束执行。

$Procedure1$ 在时间戳 $6$ 的开始再次执行，执行 $4$ 个单位时间，于时间戳 $9$ 的末尾结束执行。

$Procedure0$ 在时间戳 $10$ 的开始恢复执行，执行 $1$ 个单位时间。

所以 $Procedure0$ 总共执行 $2+1=3$ 个单位时间，$Procedure1$ 总共执行 $4$ 个单位时间。

样例2

输入

2 6
0 0 0
1 0 2
1 0 5
1 1 10
1 1 11
0 1 12

输出

3 6

说明

$Procedure0$ 在时间戳 $0$ 的开始执行，执行 $2$ 个单位时间，于时间戳 $1$ 的末尾结束执行。

$Procedure1$ 在时间戳 $2$ 的开始执行，执行 $3$ 个单位时间，于时间戳 $4$ 的末尾结束执行。

$Procedure1$ 在时间戳 $5$ 的开始递归调用自己(记为 $Procedure 1$')执行 $6$ 个单位时间，于时间戳 $10$ 的末尾结束执行。

$Procedure1$ 在时间戳 $11$ 的开始恢复执行，执行 $1$ 个单位时间。

$Procedure0$ 在时间 $12$ 的开始恢复执行，执行 $1$ 个单位时间。

所以 $Procedure0$ 总共执行 $2+1=3$ 个单位时间，$Procedure1$总共执行 $3+1=4$ 个单位时间。$Procedure1'$总共执行 $6$ 个单位时间。所以 $Procedure 1$ 取最大的执行时间即 $5$ .