939 - Genes

基因遺傳實驗室 (GEL) 研究許多遺傳疾病數年了，也收集大量疾病的資料，對於每個人可以得知道基因是否為顯性(dominant)、隱性(recessive)或者是不存在(non-existent)，基於研究資料可以得知從父母的疾病是否會遺傳給他們的孩子。然而，檢查這些推論是乏味且繁瑣的， GEL 希望你寫個自動處理的程序給他們。

想法很簡單，你將會有父子關係，以及固定的推論，計算所有人的基因是否有這段基因，如果有的話，則決定是否為顯性還是隱性。如果推論有所錯誤的話，這將會給研究人員改善推論的線索，測資中不會存在解不出來或錯誤的推論。

給定父子關係，以及部分人的基因狀態，計算所有資料中的人的基因狀態。
推論的方式如下：

• 孩子有這段基因  if and only if 父母皆有這段基因、或者父母其中一人有顯性基因。
• 孩子的基因是顯性 if and only if 父母都是顯性基因、或者其中一個人是顯性另一個人是隱性。

Input

第一行將會有一個整數 N (1 <= N <= 3100)，表示接下來會有多少行的描述。
接下來會有 N 行，每行上兩個非空字串，每個字串最多 20 個字元，且不會包含空字元。

第一個字串是這個人的名字，而第二個字串會是

1. "non-existent", "recessive", "dominant" 或
2. 他的孩子名字

第一種表示這個人的基因狀態，第二種則表示父子關係。

所有的人名都是獨特的，且不會有人的名字為 "non-existent", "recessive",  "dominant"，對於每個人要不存在兩個父母，要不沒有父母。

Output

對於每組測資，輸出每個人的基因狀態，按照字典順序輸出。
第一個字串為人名，第二個字串為基因狀態，中間以一個空白隔開。

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