Get Function Execution Time

Based on start/end logs sorted by time, compute the exclusive CPU time of each function; the timestamp at which a call ends is also counted.

输入格式

The first line contains n m; then m lines of function_id:start:timestamp or function_id:end:timestamp. The logs form a valid nested call sequence. This site adds timestamp≤1000000.

输出格式

Output n exclusive times, separated by spaces.

样例 1

输入：

3 6
0:start:0
2:start:4
2:end:5
1:start:7
1:end:10
0:end:11

输出：

6 4 2

样例 2

输入：

1 2
0:start:2
0:end:4

输出：

3

样例 3

输入：

2 4
0:start:0
1:start:1
1:end:1
0:end:2

输出：

2 1