Find Relevant Events

You are given a list of events, each event having a timestamp and an event type. You are also provided with two integers: \(T\), the number of different event types (numbered from 1 to \(T\)), and \(K\), the size of the time window in seconds.

The events are processed in chronological order. For each event encountered, you need to update the record for that event type with its timestamp. In addition, for every other event type, if the recorded timestamp is older than \(K\) seconds relative to the current event's timestamp, it should be invalidated (set to None). In the end, for each event type from 1 to \(T\), output the last valid timestamp (in the format "YYYY-MM-DD HH:MM:SS") if available; otherwise, output "None".

Note: All timestamps provided in the input are valid and follow the format "YYYY-MM-DD HH:MM:SS".

inputFormat

The first line contains two integers \(T\) and \(K\) separated by a space, where \(T\) is the number of event types and \(K\) is the time window size in seconds.

The second line contains an integer \(N\), the number of events.

Each of the following \(N\) lines contains a timestamp and an event type separated by a space. The timestamp is in the format "YYYY-MM-DD HH:MM:SS" and the event type is an integer.

Input is read from standard input (stdin).

outputFormat

Output \(T\) lines. Each line corresponds to the most recent valid event timestamp for event types 1 through \(T\), in order. If no valid event exists for a type, output "None" (without quotes).

Output is written to standard output (stdout).

## sample

2 30
4
2023-10-01 08:00:00 1
2023-10-01 08:00:35 2
2023-10-01 08:01:00 1
2023-10-01 08:01:30 2

2023-10-01 08:01:00
2023-10-01 08:01:30

</p>