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.


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.


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

Input Sample Output Sample

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