Median Log Identifier

You are given a series of logs. Each log contains a unique identifier and a timestamp in the format \(YYYY-MM-DD\ HH:MM:SS\). Your task is to determine the log whose timestamp is the median of all timestamps when they are sorted in non-decreasing order.

If there is an even number of logs, the median is defined as the log at index \(\lfloor\frac{n-1}{2}\rfloor\) after sorting (i.e. the earlier of the two middle logs). The answer should be the identifier of that log.

Note: It is guaranteed that all timestamps are in a valid format and each identifier is unique.

inputFormat

The input is read from standard input and has the following format:

n
id1 YYYY-MM-DD HH:MM:SS
id2 YYYY-MM-DD HH:MM:SS
...        
idn YYYY-MM-DD HH:MM:SS

Here, the first line contains an integer \(n\) representing the number of logs. Each of the next \(n\) lines contains a log identifier followed by a timestamp (the timestamp consists of two parts separated by a space).

outputFormat

Output a single line to standard output containing the identifier of the log at the median timestamp after sorting.

3
log1 2023-01-01 12:00:00
log2 2023-01-01 13:00:00
log3 2023-01-01 14:00:00

log2