Genealogical Research

These days everyone seems to be researching their ancestry. Such research is usually done with family-history software sold by a number of vendors. Unfortunately that software is expensive and runs only on the McDoze X operating system, so you are to write an open-source equivalent.

Your program reads a series of commands, one per line. The commands follow this grammar:

command     ::= birth
            ::= death
            ::= ancestors
            ::= descendants
            ::= QUIT

birth       ::= BIRTH child : date : mother : father
death       ::= DEATH person : date
ancestors   ::= ANCESTORS person
descendants ::= DESCENDANTS person

child       ::= name
mother      ::= name
father      ::= name
person      ::= name
date        ::= name

name        ::= any sequence of characters that does not begin or end
                with a space and does not contain a colon

Spaces in the input are ignored except when they appear inside a name. The BIRTH and DEATH commands record a person's birth and death; you may assume that every person has a unique name. The ANCESTORS and DESCENDANTS commands are queries: they print a family tree, or a reverse family tree, for the named person using the information from previous BIRTH and DEATH commands. The QUIT command marks the end of the input.

The BIRTH, DEATH, and QUIT commands produce no output. For each ANCESTORS (DESCENDANTS) command, print the following:

1. A line containing "ANCESTORS of" ("DESCENDANTS of") followed by the person's name.
2. Indented 2 spaces from the previous line, the person's first parent (child) in alphabetical order, followed by that parent's (child's) birth date, then a space, then a hyphen; if the parent (child) has died, add another space and the date of death. If there is no birth record for the parent (child), print the name alone.
3. The ancestor (descendant) information for that parent (child), indented another 2 spaces, using these same steps (steps 2-4).
4. Repeat steps 2-4 for the remaining parents (children), using the same indentation as the previous parent (child).

Leave one empty line between the outputs of successive commands.

Constraints:

• No input line exceeds 100 characters.
• There are at most 250 lines of input.
• Every DEATH, ANCESTORS, and DESCENDANTS command refers to a name that has already appeared in a BIRTH command.
• QUIT appears only as the last line of the input.