A debounced function waits until calls stop for a while before it runs. Each call (re)starts a timer of d milliseconds; the real work runs only when a timer finishes without being restarted.
You are given the times of n calls, in non-decreasing order. Print the times at which the real work runs.
Rules:
- A call at time
tsets the timer to fire att + d, cancelling any timer that is still waiting. - If a call arrives at exactly the moment a timer is due, the timer fires first, and then the call starts a new timer.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ d ≤ 10^6
- 0 ≤ each time ≤ 10^9, given in non-decreasing order
Input and output
- Input
- Line 1: n and d Line 2: n call times
- Output
- The fire times in increasing order, separated by single spaces.
Examples
Input 1
5 3
1 2 3 8 12Output
6 11 15Calls at 1, 2, 3 keep resetting the timer, which finally fires at 3 + 3 = 6. The call at 8 fires at 11, before the call at 12, which fires at 15.
Input 2
3 5
0 4 9Output
9 14The gap 4 → 9 is exactly 5, so the timer from 4 fires at 9 before the call at 9 is handled.
Show hints
- A call is the last one of its burst when the next call comes at or after its own deadline.
- You do not need to simulate every millisecond.
Show the explanation
Call i causes a fire exactly when nothing cancels its timer, that is, when it is the last call or the next call comes at time t[i+1] ≥ t[i] + d. The fire then happens at t[i] + d. One pass over the list is enough.
This is the same logic as a debounce(fn, d) helper written with a closure that keeps the timer id and calls clearTimeout before each new setTimeout, and as the useDebouncedValue hook pattern in React search boxes.
Original UniCircle question. Last reviewed 22 Oct 2026.