Royal Family Tree

/problems/royalfamilytree/file/statement/en/img-0001.jpg
Crown image by Brian Goff (Shutterstock), Tree image by Nikitina Olga (Shutterstock); Used under license

On September 9, 2015, Queen Elizabeth II became the longest reigning monarch in the history of the British Empire, surpassing the record set by her great-great-grandmother, Queen Victoria. This landmark event prompted many people to think about royal succession. Who is first in line to succeed Elizabeth II? Who is second in line? What is the rule?

For centuries, British royal succession favoured older male children and their descendants. (In early 2015, this gender bias, called male-preference primogeniture, was replaced by a gender-neutral policy, called absolute primogeniture, for members of the royal family born after October 28, 2011, but for the purposes of this problem, limit your consideration to the traditional system.) More specifically, suppose the current monarch has male children $m_1, m_2, \ldots $, ordered from oldest to youngest, and female children $f_1, f_2, \ldots $, ordered from oldest to youngest. Succession passes from the monarch to $m_1$ and his descendants, then to $m_2$ and his descendants, etc., until all the $m_ i$ have been included. After this, succession passes to $f_1$ and her descendants, then to $f_2$ and her descendants, etc., until all the $f_ j$ have been included. This same rule applies everywhere in the royal family tree, i.e., if $X$ is any descendant of the monarch, then saying “succession passes to $X$ and his/her descendants” means that succession passes first to $X$, and then to the children of $X$ in the same way that succession passed to the children of the monarch.

For this problem, you will be given a description of a royal family tree, with the monarch as the root, and you will be asked to respond to one or more queries about the order of succession. As an example, Sample Input 1 corresponds to the British royal family tree in late 2016, with Queen Elizabeth II as the monarch.

Input

Input consists of a single case. The first line contains three space-separated integers, $N\ Q\ Y$ ($1 \leq N \leq 5\, 000$, $1 \leq Q \leq 100$, and $1\, 000 \leq Y \leq 3\, 000$), where $N$ is the number of people in the royal family tree other than the monarch, $Q$ is the number of queries to which you must respond, and $Y$ is the year in which the monarch was born. This is followed by $N$ lines of the form $c\ p\ g\ y$, where $c$ and $p$ are names (nonempty strings of length at most $20$ consisting of uppercase letters (AZ) and underscores (_) only), indicating that $c$ is a child of $p$; $g$ (gender) is either F or M, indicating that $c$ is female or male, respectively; and $y$ is an integer indicating the year in which $c$ was born (see below for bounds on $y$). Then follow $Q$ lines, each containing a single integer, $n$ $(0 \leq n \leq N)$, where $n$ corresponds to a query of the form “Who is $n^{\mathrm{th}}$ in the order of succession?”

Note: It is guaranteed that the $N$ lines giving the parent-child relationships correctly specify a family tree structure. In particular:

  • there is exactly one person who appears as a parent but not as a child; this is the monarch

  • there is exactly one (simple) path from each non-monarch person to the monarch

In addition:

  • no two distinct persons in the family tree have the same name

  • no two distinct children of the same person have the same year of birth

  • if $p$ is the parent of $c$, $y_ p$ is $p$’s year of birth, and $y_ c$ is $c$’s year of birth, then

    \[ y_ p < y_ c \leq y_ p+100 \]

Output

For each query, $n$, output a single line containing $n$, followed by a space, followed by the name of the person who is $n^{\mathrm{th}}$ in the line of succession. Note that the monarch is $0^{\mathrm{th}}$ in the line of succession, the person who will succeed the monarch is $1^{\mathrm{st}}$ in the line of succession, etc.

Sample Input 1 Sample Output 1
17 5 1926
CHARLOTTE WILLIAM F 2015
PETER ANNE M 1977
EDWARD ELIZABETH_II M 1964
MIA ZARA F 2014
WILLIAM CHARLES M 1982
BEATRICE ANDREW F 1988
ISLA PETER F 2012
LOUISE EDWARD F 2003
GEORGE WILLIAM M 2013
ANDREW ELIZABETH_II M 1960
ZARA ANNE F 1981
EUGENIE ANDREW F 1990
CHARLES ELIZABETH_II M 1948
JAMES EDWARD M 2007
ANNE ELIZABETH_II F 1950
SAVANNAH PETER F 2010
HENRY CHARLES M 1984
13
1
0
9
4
13 PETER
1 CHARLES
0 ELIZABETH_II
9 EDWARD
4 CHARLOTTE