Get Total Execution Time

Given the actual call log of a single thread, compute the exclusive time of each function summed over all its calls. A start log takes over the CPU at the beginning of that second, an end log includes that second, and after a return the previous call resumes; recursion is allowed.

输入格式

The first line contains n m, followed by m lines of id:start/end:timestamp. 1≤n≤100, 1≤m≤500, each ID is in 0..n−1, and times are 0..1000 and non-decreasing; start times are distinct, end times are distinct, and every start has an end. The log represents a valid call-stack execution: a paused call cannot end first.

输出格式

Output n integers, for ID 0 through ID n−1 in order.

样例 1

输入：

2 4
0:start:0
1:start:3
1:end:6
0:end:10

输出：

7 4

样例 2

输入：

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

输出：

1

样例 3

输入：

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

输出：

2 1

样例说明

The examples give 7 4; 1; and 2 1 respectively.