A. Construction plan
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

A team of engineers is planning the construction of a new factory. For their factory to be reliable, they want to create various items at a constant and reliable rate of units per second. They can use different crafting stations to craft these materials. Each crafting station has its own speed, affecting a crafting process. Each material has its own crafting recipe that has to be executed in a specific crafting station.

You are given the description of every crafting station together with the recipes for every material and intermediate material that you need. You are also given a list of materials that you have to produce at a certain rate so that your factory is reliable.

We consider a configuration of machines to be optimal if by removing any of the machines from the configuration, there is at least a material such that its production rate is smaller than the required amount.

Input

The first line of input will contain an integer $$$M$$$ ($$$1 \leq M \leq 100$$$) representing the number of types of machines we have. On each of the following $$$M$$$ lines there will be a string $$$n$$$, or ($$$1 \leq |n| \leq 30$$$) and a number $$$s$$$ ($$$0.01 \leq s \leq 100$$$) representing the name and the speed-rate of one machine.

The following line of input will contain an integer $$$N$$$ ($$$1 \leq N \leq 100$$$) representing the number of recipes.

Following $$$N$$$, there will be the description of each recipe. On the first line of a recipe, there is the string $$$p$$$ ($$$1 \leq |p| \leq 30$$$) representing the name of the material to be crafted, another string $$$l$$$ ($$$1 \leq |l| \leq 30$$$) representing the name of the crafting station used during the process and a number $$$t$$$ ($$$0.01 \leq t \leq 100$$$), representing the time needed to craft the material on normal speed in seconds. On the following line, there is a number $$$k$$$ ($$$0 \leq k \leq 15$$$) representing the number of materials needed during production.

Each of the following $$$k$$$ lines will contain a string $$$n$$$ ($$$1 \leq |n| \leq 30$$$) representing the name of a required material and an integer $$$c$$$ ($$$1 \leq c \leq 10$$$) representing the number of units of the corresponding material required in the process.

Suppose that a recipe takes $$$t$$$ seconds to craft in normal speed. That is, given a machine with speed $$$1$$$ and the required materials, it would take $$$t$$$ seconds to craft the recipe. On the other hand, if the speed is $$$0.5$$$, the machine would be two times slower than normal, therefore after feeding it the required materials, it would take twice as long to craft. That is, the recipe would be executed in $$$2 \times t$$$ seconds.

Each recipe requires exactly one machine of type $$$l$$$. After a recipe is executed, we will obtain exactly one material $$$p$$$.

The next line will contain an integer $$$Q$$$ ($$$1 \leq Q \leq 100$$$) representing the number of required materials to be produced.

Each of the following $$$Q$$$ lines will contain a string $$$m$$$ ($$$1 \leq |m| \leq 30$$$) representing the name of a required material to be produced, and an integer $$$c$$$ ($$$1 \leq c \leq 10$$$) representing the number of units of that material required to be produced per second.

The numbers $$$s$$$ and $$$t$$$ are given as floating points with exactly two decimal places.

It is guaranteed that there exists a valid configuration.

It is guaranteed that the rate of production for every material in the optimal solution does not exceed $$$10^9$$$ units per second.

Each material can be crafted using a unique recipe.

It is guaranteed that there are no cyclic dependencies. That is, there is no sequence of recipes $$$r_1, r_2,\dots, r_k$$$ such that $$$\forall i\ s.t.\ 1 \leq i \lt k$$$ the recipe $$$r_i$$$ requires you to craft recipe $$$r_{i+1}$$$, and recipe $$$r_k$$$ requires you to craft recipe $$$r_1$$$.

It is guaranteed that any string read contains only lower-case letters from the English alphabet and underscores (character '_').

Output

The output should contain $$$N$$$ lines. On the $$$i$$$-th line you have to output $$$p_i$$$ $$$l_i$$$ $$$r_i$$$ where $$$r_i$$$ represents the number of machines required to execute the $$$i$$$-th recipe.

Examples
Input
3
assembler 0.50
furnace 0.50
mining_well 0.55
6
iron_plate furnace 3.20
1
iron_ore 1
copper_plate furnace 3.20
1
copper_ore 1
iron_ore mining_well 1.00
0
copper_ore mining_well 1.00
0
copper_cable assembler 0.50
1
copper_plate 1
electronic_circuit assembler 0.50
2
iron_plate 1
copper_cable 3
1
electronic_circuit 10
Output
iron_plate furnace 64
copper_plate furnace 192
iron_ore mining_well 19
copper_ore mining_well 55
copper_cable assembler 30
electronic_circuit assembler 10
Input
3
assembler 0.50
furnace 0.50
mining_well 0.55
4
iron_plate furnace 3.20
1
iron_ore 1
iron_ore mining_well 1.00
0
iron_gear assembler 0.50
1
iron_plate 2
transport_belt assembler 0.50
2
iron_plate 1
iron_gear 1
1
transport_belt 7
Output
iron_plate furnace 135
iron_ore mining_well 39
iron_gear assembler 7
transport_belt assembler 7
Note

In the first example, because the assembler has a speed of 0.50 and the recipe for crafting an electronic circuit takes 0.50 seconds to craft an item, we will craft one electronic circuit per second for each assembler we have. Because we need to have a rate of production of 10 units per second, we will require 10 assemblers.

Each assembler used for the production of electronic circuits requires one iron plate, so we need a production rate of $$$10$$$ iron plates per second. We can use the first recipe to craft iron plates, which take $$$3.2 / 0.5 = 6.4$$$ seconds to craft each, so we need $$$64$$$ furnaces for iron plates. Each furnace needs an iron ore to complete the task so we will require $$$10$$$ iron ores per second to sustain the process. Using the third recipe, we will require $$$19$$$ mining wells to craft $$$0.55 \times 19 = 10.45$$$ iron ores per second. If we used only 18 mining wells for this recipe, we would have only crafted $$$0.55 \times 18 = 9.9$$$ iron ores per second, which is less then the rate of $$$10$$$ iron ores per second required.