In 1701, the British parliament passed the Act of Settlement, which describes the succession of the British monarch.
The algorithm of succession can be described as "the crown" moving to different people.
The rules are as follows:
- The crown begins at the current monarch.
- The crown moves to the oldest son of the current person, whether dead or alive.
- If this person has already been visited, move to the next sibling based on the priority of gender and age.
- If the current person has no sons, the crown moves to the oldest daughter.
- If at a dead end (no valid children and current person is not alive), move to the parent of the current person and apply rule again.
- If the current person is alive, they become the monarch. Otherwise, repeat step .
The British government has asked you to help them determine the next monarch, can you help them?
The first line of input will contain one integer, , the number of people in the family tree.
The next lines each contain a description of a person. Line describes the person.
Each line contains three space separated strings and one integer, in the following order:
- , the person's name (the length of which will be less than or equal to characters)
- , the gender of the person (either
- , whether the person is alive or not (either
- , the person's age in minutes .
The name and age of any given person is guaranteed to be unique.
The next lines each contain space separated strings, and , which describes that person has a child named . It is guaranteed .
The next line will contain a string, the current monarch's name.
It is guaranteed the connections form a valid family tree.
The output will contain a single string, the name of the next monarch. It is guaranteed that one will exist.
Subtask 1 [50%]
Subtask 2 [50%]
No further constraints.
Sample Input 1
4 ShaniyaGorczany female dead 19403 MsAnissaEichmann male alive 12417 LottieErnser female alive 33512 NeomaEmard female alive 82224 ShaniyaGorczany MsAnissaEichmann ShaniyaGorczany LottieErnser ShaniyaGorczany NeomaEmard ShaniyaGorczany
Sample Output 1
Explanation for Sample 1
The crown favors males, so even though
LottieErnser are both older,
MsAnissaEichmann gets the crown as the oldest living son.
Sample Input 2
4 MurlGutmannSr male dead 91182 DrMayeThompson female alive 75982 BarneyReilly female alive 92830 AndreCarroll female alive 64179 MurlGutmannSr DrMayeThompson MurlGutmannSr BarneyReilly MurlGutmannSr AndreCarroll DrMayeThompson
Sample Output 2
Explanation for Sample 2
We begin at a dead end (no children), so we back up to
MurlGutmannSr and go to the oldest female,
DrMayeThompson has already been visited so there are no more males that could be chosen.