URI Online Judge | 3035

Piece Factory

By Pedro Rey BR Brazil

Timelimit: 1

At the company's "Blocks to Build" factory, its products are toys consisting of several parts of two types: simple parts and composite parts.

All simple parts come at a price. The composite parts consist of several other part (which can be simple or composite) of various types. The price of a composite part is the sum of the price of its constituent parts.

The boss, Mr. Brick, asks you to implement an algorithm that, given a set of pieces, calculates the price of all composite parts.

Input

The first line of the entry consists of a number N which is the number of simple parts. In the next N lines, there will be a pair (P, C) where P is a string with the part name and C is the cost of the part. In the next few lines there will be a triple (P1, P2, Q) where P1 is the composite part name, P2 is the name of one of the parts that makes up P1, and Q is the quantity of part P2 in part P1.

The file ends with EOF.

Output

One should print the name of the compound part and next to it, its price, separated by a space.

Input Sample Output Sample

3
A 3
B 4
C 1
D A 2
E D 1
E A 4
D B 3
F E 3
F B 10

D 18
E 30
F 130