Function Time Profiler

A profiler watched a single-threaded program and logged every start and end of a function call, in time order, as strings such as "main start 12" and "main end 15" (the number is the time in milliseconds). Only one call runs at a time: when a call starts, the one that was running pauses until the new call ends. Functions may call other functions or themselves, and every start has a matching end.

Write exclusive_times(logs) that works out each function's own time: the total time, over all of its calls, during which that function was the one running, leaving out the time it spent waiting for the calls it made. Return a list of (name, time) tuples sorted by name.

Examples

exclusive_times(["main start 0", "load start 2", "load end 5", "main end 9"])
# returns [('load', 3), ('main', 6)]
exclusive_times(["fib start 0", "fib start 1", "fib end 4", "fib end 6"])  # returns [('fib', 6)]
exclusive_times(["a start 5", "b start 5", "b end 5", "a end 8"])          # returns [('a', 3), ('b', 0)]

In the first example main runs from 0 to 2, waits while load runs from 2 to 5, then runs again from 5 to 9, so its own time is 2 + 4 = 6. In the second, the outer fib call runs from 0 to 1 and from 4 to 6, the inner one from 1 to 4, so fib totals 6.

Constraints

• 0 <= len(logs) <= 20,000
• Times are whole numbers from 0 to 1,000,000,000 and never go down.
• Names are lowercase letters, digits and underscores.

Note

Time when no call is running (between two top-level calls) belongs to nobody. A call that starts and ends at the same moment still appears, with a time of 0.