Problem H
Royal Family Tree
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 (A–Z) 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 |
