For many years, the Genetic Evolution Laboratory (GEL) has been studying the evolution of various genetic diseases, by collecting, for each disease, data from a large population, over several generations. For each person, it is known whether the gene is dominant, recessive, or non-existent. Based on this data, scientists formulate an hypothesis on how the disease is transmitted from parents to children. However, it is tedious to check by hand if the data matches the hypothesis, so GEL asked you to automate this task for them. The idea is simple: the program will, given the parent-child relationships and a fixed hypothesis, calculate for all people whether they have the gene or not, and in the former case whether it is dominant or not. This result is written to a text file, which will later be compared (using a standard file differencing tool) with the data that GEL collected. If there are no differences, the hypothesis is valid. Any mismatch will give clues to GEL’s scientists on how they should improve the hypothesis. Given a set of parent-child relationships, and the status of the gene for all those people whose parents are not in the data set, compute the status of the gene for all people in the data set, according to the following hypothesis: • the child has the gene if, and only if, both parents have it or it is dominant in one of the parents; and • the child’s gene is dominant if, and only if, the gene is dominant in both parents or dominant in one and recessive in the other parent. Input The first line contains an integer N (1 ≤ N ≤ 3100), which is the number of lines of the data set. Each of the following N lines contains a pair of non-empty strings, separated by a space. All strings are at most 20 characters long, and no string contains a blank (tab or space). The first string is the name of a person. The second string is either
2/2 Sample Input 7 John dominant Mary recessive John Susan Mary Susan Peter non-existent Susan Marta Peter Marta Sample Output John dominant Marta recessive Mary recessive Peter non-existent Susan dominant