The Out-of-Order Stream Deduplicator

You are processing a stream of events. Each event has an ID and a timestamp. Events can arrive out of chronological order. An event is considered a 'Valid Unique' if its ID has not appeared in the last K seconds of *simulation time*. Simulation time is defined as the maximum timestamp seen so far minus K. Specifically: When an event (ID, T) arrives: 1. Update the current 'global time' to max(global_time, T). 2. Expire all records of IDs that occurred at time <= global_time - K. 3. If the ID is not currently tracked, it is 'Valid'. Record it and print its ID. 4. If the ID is tracked, it is a 'Duplicate'. Ignore it. Input: First line is K (seconds). Second line is N (number of events). Next N lines are `ID Timestamp`. Output: The IDs of all 'Valid' events in the order they were processed. Example: Input: 10 4 USR1 100 USR2 105 USR1 108 USR2 116 Output: USR1 USR2 USR2