Problem D
Chemical Equations

Bob is a master chemist and he has a list of $N$ different chemical equations that detail how to create specific compounds. Each chemical equation consists of a compound and $R$ reactants with associated quantities that can be used to make the compound. A “base compound” is defined as a reactant that cannot be further reduced into other reactants according to the list of chemical equations. Given this list of chemical equations and a compound that is in the list of chemical equations (possibly only as a reactant), output an alphabetized list of base compounds and quantities that can be used to form the given compound. Note that the chemical equation that forms the given compound will not necessarily contain only base compounds. You are guaranteed that the list of chemical equations will not form a cycle, meaning that there exists no compound that can be used to make its constituent reactants. Additionally, there will be at most one equation detailing how to create a compound for each compound, so there will be a single unique answer.

It is guaranteed that final quantities in your answer will fit into a 32-bit signed integer.

Input

The first line contains a single integer $N$ such that $1 \leq N \leq 50$. Next will follow $N$ chemical equations.

Each chemical equation starts with a line that gives the name of the compound as a string followed by an integer, $R$, with $1 \leq R \leq 10$, indicating that $R$ reactants are used to make the compound. The next $R$ lines of the chemical equation each consist of an integer $q_ i$ (the quantity of the component reactant needed to make the compound), with $1 \leq q_ i \leq 3$, and the name of the component reactant given as a string.

The final line of the input will contain a compound name that was previously in the list of chemical equations. You will output all the base compounds that are needed to form this compound.

Output

Given that you can form the desired compound with $B$ base compounds, output $B$ lines sorted alphabetically, with the $i$th line containing the $i$th base compound’s name and the quantity of that base compound needed to form the given compound.

1
AL2O3 2
2 AL
3 O
AL2O3

AL 2
O 3

2
CO2 2
1 C
1 O2
O2 1
2 O
CO2

C 1
O 2