Marathon Checkpoints Analysis

A city is hosting a marathon where each runner is assigned a unique bib number from 1 to N. Throughout the race, multiple checkpoints record the time at which a runner passes by. Each record provides a runner's bib number, a checkpoint number, and the time at which the runner passed that checkpoint.

Your task is to analyze the data to determine the runner who has passed through the largest number of distinct checkpoints. In case of a tie (i.e. multiple runners passing through the same maximum number of distinct checkpoints), return the runner with the smallest bib number. If no records are provided, then output \(None\).

Mathematically, for each runner \(r\), let \(S(r)\) be the set of checkpoints passed. You are to compute the runner \(r^*\) such that \[ r^* = \min \{ r : |S(r)| = \max_{i} |S(i)| \}. \]

inputFormat

The input is provided via standard input (stdin) and has the following format:

N M C
bib1 checkpoint1 time1
bib2 checkpoint2 time2
... (C records in total)

Where:

• N is the total number of runners.
• M is the total number of checkpoints.
• C is the number of records.
• Each of the next C lines contains three integers: the runner's bib number, the checkpoint number, and the time (in milliseconds) when the runner passed that checkpoint.

outputFormat

The output should be printed to standard output (stdout) as a single line containing the bib number of the runner who passed the maximum number of distinct checkpoints. If there are no records, print None.

5 4 11
1 1 500
1 2 1000
2 1 700
2 2 1500
3 1 300
3 3 1300
4 2 500
4 3 1400
4 4 2000
5 1 100
5 4 1800

4