Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Facetook Priority Wall

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFacetook is a well known social network website, and it will launch a new feature called Facetook Priority Wall. This feature will sort all posts from your friends according to the priority factor (it will be described).

This priority factor will be affected by three types of actions:

- 1. "
*X*posted on*Y*'s wall" (15 points), - 2. "
*X*commented on*Y*'s post" (10 points), - 3. "
*X*likes*Y*'s post" (5 points).

*X* and *Y* will be two distinct names. And each action will increase the priority factor between *X* and *Y* (and vice versa) by the above value of points (the priority factor between *X* and *Y* is the same as the priority factor between *Y* and *X*).

You will be given *n* actions with the above format (without the action number and the number of points), and you have to print all the distinct names in these actions sorted according to the priority factor with you.

Input

The first line contains your name. The second line contains an integer *n*, which is the number of actions (1 ≤ *n* ≤ 100). Then *n* lines follow, it is guaranteed that each one contains exactly 1 action in the format given above. There is exactly one space between each two words in a line, and there are no extra spaces. All the letters are lowercase. All names in the input will consist of at least 1 letter and at most 10 small Latin letters.

Output

Print *m* lines, where *m* is the number of distinct names in the input (excluding yourself). Each line should contain just 1 name. The names should be sorted according to the priority factor with you in the descending order (the highest priority factor should come first). If two or more names have the same priority factor, print them in the alphabetical (lexicographical) order.

Note, that you should output all the names that are present in the input data (excluding yourself), even if that person has a zero priority factor.

The lexicographical comparison is performed by the standard "<" operator in modern programming languages. The line *a* is lexicographically smaller than the line *b*, if either *a* is the prefix of *b*, or if exists such an *i* (1 ≤ *i* ≤ *min*(|*a*|, |*b*|)), that *a*_{i} < *b*_{i}, and for any *j* (1 ≤ *j* < *i*) *a*_{j} = *b*_{j}, where |*a*| and |*b*| stand for the lengths of strings *a* and *b* correspondently.

Examples

Input

ahmed

3

ahmed posted on fatma's wall

fatma commented on ahmed's post

mona likes ahmed's post

Output

fatma

mona

Input

aba

1

likes likes posted's post

Output

likes

posted

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/27/2021 23:09:52 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|