Service Call Profiler

Uber runs a profiler over a backend that executes on a single thread. A service can call other services, and a call may even re-enter the same service, so calls nest like a call stack: when one service starts, whichever service was running is paused and resumes only once the inner call finishes. You are given the profiler log in execution order. Each entry has the form "<id>:start:<timestamp>" or "<id>:end:<timestamp>". - "<id>:start:<t>" means service id began running at the very start of time unit t. - "<id>:end:<t>" means service id finished at the very end of time unit t, so it was still running for the whole of time unit t. Timestamps are non-decreasing, every start has a matching end, and the log is consistent with a single thread. Report the exclusive time of every service: how many time units it spent running itself, not counting time while it was paused waiting on a nested call. Input format: - First line: two integers N and M, the number of services and the number of log entries - Next M lines: one log entry each Print N space-separated integers, where the value at index i is the exclusive time of service i. The answer can exceed a 32-bit integer.

1 <= N <= 100
2 <= M <= 10^5, and M is even
0 <= id < N
0 <= timestamp <= 10^9

2 4
0:start:0
1:start:2
1:end:5
0:end:6

3 4

1 6
0:start:0
0:start:2
0:end:5
0:start:6
0:end:6
0:end:7

8