Guildhall Standout Adventurers

The Ironvale Guildhall keeps a log of how many quests every adventurer has completed in each quest category they've attempted. For a given quest category, define its guild average as the mean of the completion counts recorded for that category, taken over every adventurer who has a record in it (including the adventurer in question).

An adventurer is a Standout if there is at least one quest category in their own record where their completion count is strictly greater than that category's guild average.

Given every recorded (adventurer id, quest category, completions) entry, find every Standout adventurer.

Input format

The first line contains a single integer N, the number of records. Each of the next N lines contains an adventurer id (integer), a quest category (a token of 1 to 20 lowercase English letters), and a completions count (integer), separated by single spaces. No two records share the same (adventurer id, quest category) pair.

Output format

Print the ids of every Standout adventurer, in strictly increasing order, separated by single spaces on one line. If no adventurer qualifies, print an empty line.

Constraints

1 <= N <= 10000 1 <= adventurer id <= 100000 0 <= completions count <= 1000000

4
1 hunting 10
2 hunting 20
1 mining 5
3 mining 5

2

6
5 fishing 8
6 fishing 2
8 fishing 50
5 mining 100
7 mining 1
6 mining 1

5 8