A sampling profiler wakes the target thread at fixed instants and records its call stack. You are given those samples in strictly increasing timestamp order, and you must turn the *changes* between them into a stream of `START` / `END` events, one pair per function activation. Each sample is a pair `(timestamp, stack)`. `stack` lists function names from the outermost call to the currently executing function, so `stack[0]` is the outermost frame and the last element is the innermost one. An empty stack means nothing was running at that instant. The stack in force before the first sample is empty. Implement `profiling_events(samples, n)`. Return the list of events, each event a triple `[timestamp, type, function]` where `type` is the string `"START"` or the string `"END"`. ## Frame identity A *frame* is identified by three things together: its depth in the stack, its function name, and the exact sequence of ancestors above it. `b` at depth 1 under `a` and `b` at depth 1 under `c` are two different frames, and so are `b` at depth 1 and `b` at depth 2. A frame is **present** in a sample when that sample's stack is at least that deep and its prefix, up to and including that depth, equals the frame's own prefix. Otherwise the frame is **absent**. ## Debouncing `n` is a debounce threshold, and it is applied to each frame independently -- never to the complete stack. - An inactive frame becomes active once it has been present in `n` consecutive samples. Its `START` carries the timestamp of the **first** sample of that run, even though the run is only confirmed at the last sample of the run. - An active frame becomes inactive once it has been absent from `n` consecutive samples. Its `END` carries the timestamp of the **first** sample of that absence run, again even though the run is only confirmed later. - A presence or absence run shorter than `n` is transient: it emits nothing, and it resets the opposing counter. - One run can confirm several frames at once. If a stack `[a, b]` first appears and then persists for `n` samples, `a` and `b` both start at that first sample's timestamp. - Churn deep in the stack must not reset an unchanged outer frame's counter, because the outer frame's identity does not mention anything below it. - A frame can only be present when every one of its ancestors is present, so no frame ever outlives an ancestor. - With `n = 1` this reduces to comparing each stack with the previous one: the functions dropped from the common prefix end, and the functions added past the common prefix start. A function still inside the common prefix emits nothing. ## Output order Walk the samples in order. Every event confirmed while processing one sample carries one and the same timestamp; emit that sample's `END` events first, deepest frame first, and then its `START` events, outermost frame first. After the last sample has been processed, append one `END` for every frame that is still active, deepest frame first, all stamped with the **last sample's** timestamp. ## Examples **Example 1.** `n = 1`, `samples = [(10, ["A", "B"]), (20, ["A", "C"]), (30, [])]` Output: ```text [[10, "START", "A"], [10, "START", "B"], [20, "END", "B"], [20, "START", "C"], [30, "END", "C"], [30, "END", "A"]] ``` `A` is untouched by the second sample because it stays in the common prefix. At timestamp 30 the stack empties, so both surviving frames end there, deepest first. **Example 2.** `n = 2`, `samples = [(10, ["A", "B"]), (20, ["A", "C"]), (30, ["A", "C"]), (40, []), (50, [])]` Output: ```text [[10, "START", "A"], [20, "START", "C"], [40, "END", "C"], [40, "END", "A"]] ``` `A` is present in the first three samples, so it starts at 10 -- the churn beneath it is irrelevant. `B` appears once only and is transient, so it never becomes active. `C` is present at 20 and 30, so it starts at 20. Both active frames are absent at 40 and 50, so both end at 40, deepest first.