Top Performing Agents

You are given data for sales agents, regions, and their sales transactions during different shifts. Each agent is assigned to a region and works one shift (morning, afternoon, or night). Each sale is recorded with a sale id, the agent id who made the sale, and the sale value.

The goal is to determine the top performing agent for each (region, shift) pair based on the following criteria:

• Highest number of sales.
• If tied, the highest total sales value.
• If still tied, the highest average sale value, where \(\text{average} = \frac{\text{total sales}}{\text{number of sales}}\).

Finally, output the results sorted primarily by region name in lexicographical order and, within the same region, according to the shift order: morning, afternoon, then night.

inputFormat

The input is read from standard input (stdin) and follows this format:

1. The first line contains three integers \(m\), \(n\), and \(p\) separated by spaces, where:
   • \(m\): number of regions.
   • \(n\): number of agents.
   • \(p\): number of sales records.
2. The next \(m\) lines each contain a region id (integer) and a region name (string), separated by space.
3. The following \(n\) lines each contain an agent id (integer), a region id (integer) and a shift (string: morning, afternoon, or night), separated by spaces.
4. The next \(p\) lines each contain a sale id (integer), an agent id (integer), and a sale value (integer), separated by spaces.

outputFormat

For each group (region, shift) that has at least one agent, output a line containing the region name, the shift, and the agent id of the top performing agent, separated by spaces. The lines should be printed in order of region name (lexicographically) and then by shift (morning, afternoon, night).

## sample

3 6 9
1 North
2 South
3 East
1 1 morning
2 1 afternoon
3 1 night
4 2 morning
5 2 night
6 3 afternoon
1 1 100
2 1 200
3 1 150
4 1 300
5 2 100
6 2 200
7 4 250
8 5 300
9 6 150

East afternoon 6
North morning 1
North afternoon 2
North night 3
South morning 4
South night 5

</p>