HNL

Interview

Time limit1sMemory limit128 MB

Summary

Given N clubs with points and one final round of matches, list every club that can still finish first under some set of results.

Level: Medium5 of 10
Topics: Brute force, Sorting, Implementation
Solved: No attempts yet

Problem

Mirko follows football closely, and the competition he likes most is the first Croatian football league. The league has $N$ clubs.

Clubs are ranked by the number of points they have won, and clubs on the same number of points are ordered alphabetically by name.

One round is left in the league. Many clubs sit within a few points of each other, so Mirko wants to know which clubs can still win the title. Write a program that answers the question for him.

You are given the current league table and the fixtures of the last round. Every team plays exactly one match. If a match ends in a draw, both teams get 1 point. Otherwise the winner gets 3 points and the loser gets 0 points.

Input

The first line contains the number of clubs in the league, $N$ ( $1 \le N \le 20$ ). $N$ is even.

Each of the next $N$ lines contains a club name and its number of points, separated by one space. A club name is a single word of uppercase English letters, and no two clubs have the same name. The number of points is a non-negative integer smaller than 100. The clubs are listed from the top of the table downwards, by the ranking rule above.

Each of the next $N/2$ lines describes one match in the form Team1 - Team2, where Team1 and Team2 are the names of the clubs playing that match. The separator between the two names is one dash character with a single space on each side. It is either the ASCII hyphen or the Unicode en dash (U+2013).

Output

Print the name of every club that has at least one scenario in which it wins the title. Print one name per line, in alphabetical order.

Hint

In the first example, if DINAMO beats ZADAR and MARSONIA draws with VINOGRADAR, DINAMO wins the title: it finishes on the same points as the other two clubs, but it comes before them alphabetically. If the match between MARSONIA and VINOGRADAR does not end in a draw, the winner of that match takes the title.

ZADAR is the only club with no way to win. If ZADAR beats DINAMO and MARSONIA draws with VINOGRADAR, ZADAR finishes on the same points as those two clubs, but it does not take the title because it comes after them alphabetically.

Examples2

Example 1

Input

4
MARSONIA 50
VINOGRADAR 50
DINAMO 48
ZADAR 48
MARSONIA – VINOGRADAR
ZADAR – DINAMO

Expected output

DINAMO
MARSONIA
VINOGRADAR

Example 2

Input

10
DINAMO 27
HAJDUK 27
LOKOMOTIVA 26
RIJEKA 26
SPLIT 19
ISTRA 17
SLAVEN 12
ZADAR 12
DRAGOVOLJAC 7
OSIJEK 7
DINAMO – HAJDUK
LOKOMOTIVA – RIJEKA
SPLIT – ZADAR
ISTRA – SLAVEN
DRAGOVOLJAC - OSIJEK

Expected output

DINAMO
HAJDUK
LOKOMOTIVA
RIJEKA