407019: GYM102688 A Functional Alchemy

Alchemy has long struggled in its most basic objective of turning lead into gold. This changed when Pyoorfan Dahlai Lahm, while working in her laboratory in Behl, discovered a catalytic element that made this transmutation much easier. This was a great accomplishment, so this element was named Dahnium in honor of Dahlai. To this day, we commemorate Dahlai even in the name of our country, Lahm Dah.

As a first-class citizen of Lahm Dah, you are of course familiar with the ten basic elements, or the ten different Tai. There are the classical Tai, which are Air, Water, Earth, and Fire. Then there are the metallic Tai, which consist of Copper, Mercury, Gold, Iron, Iodine, and Dahnium. We refer to these Tai by the first letter of their Alchemical Names, which are Aqua (Water), Breath (Air), Copper, Dahnium, Earth, Fire, Gold, Hydrargyrum (Mercury), Iron, and Jodium (Iodine).

This is the second week of your internship at Behl Labs. Like many alchemical companies, Behl Labs is situated in a classroom in the Lahm Dah Institute of Technology. Your job is to transform Tai into other Tai by applying a series of Kshons. In her time, Dahlai discovered two kinds of Kshons, which are named Pyoorfan Kshons in her honor:

1. Ankoray. In the process of Ankoraying, one Tai is turned into two of the same kind of Tai. For example, the Kshon C -> CC takes a single Copper as input, and turns it into two Coppers.

2. Pkast. One Tai can be converted into any kind of Tai through a process called Tai Pkasting. For example, the Kshon E -> * takes a single Earth as input, and turns it into any single Tai, including Earth itself.

A Kshon is extremely fragile, which is why it takes training to use them. Even with extreme care, a Kshon can only be used once, and once a Kshon is used, it cannot be used again. Because they are needed in large supply throughout the nation of Lahm Dah, special factories construct these Kshons and deliver the results to classes everywhere.

Today, your boss is unable to provide you with your usual supply of Kshons, which you suppose is a side effect of some higher-order unresolved arguments. So you need to plan the sequence of Kshons you want to use very carefully, if you do not want to be garbage collected.

You know how many of each Tai you have, and which Kshons are available. You now wonder: what is the maximum number of each Tai you can make? Since you are too lazy to evaluate this by hand, please write a program to answer this question.

The first line of input contains ten space-separated integers, $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$, $$$E$$$, $$$F$$$, $$$G$$$, $$$H$$$, $$$I$$$, and $$$J$$$ which are the number of Tai you have of Aqua, Breath, Copper, Dahnium, Earth, Fire, Gold, Hydrargyrum, Iron, and Jodium you have, respectively.

The second line of input contains one integer, $$$K$$$, the number of distinct Kshons you have.

The next $$$K$$$ lines of input each contain a positive integer $$$N$$$, followed by a space, followed by a Kshon, written in the form "x -> y" (without quotes). This represents $$$N$$$ Kshons, each that take x as input, and turns it into y. Here,

• x is one of A, B, C, ..., J, and
• y is either x twice ("xx") or *.

Output one line of ten space-separated integers, which are the maximum number of Aqua, Breath, Copper, Dahnium, Earth, Fire, Gold, Hydrargyrum, Iron, and Jodium you can make with your Kshons. Each number is independent of all the other ones.

For all subtasks

$$$0 \le A, B, \ldots, J, K, N \le 10^{12}$$$

$$$N$$$ is positive.

No two of the $$$K$$$ distinct Kshons are the same.

Subtask 1 (10 points): All Kshons are Ankoray.

Subtask 2 (10 points): All Kshons are Pkast.

Subtask 3 (16 points): The sum of all $$$N$$$s in the file is at most $$$10$$$.

Subtask 4 (11 points): No Kshon has D, E, F, G, H, I, or J as input.

Subtask 5 (9 points): No Kshon has E, F, G, H, I, or J as input.

Subtask 6 (16 points): No Kshon has G, H, I, or J as input.

Subtask 7 (12 points): No Kshon has I or J as input.

Subtask 8 (16 points): No additional restrictions.

0 0 0 0 0 0 0 0 0 0
0

0 0 0 0 0 0 0 0 0 0

3 0 0 0 0 0 0 0 0 0
3
2 A -> *
2 B -> *
1 B -> BB

4 3 3 3 3 3 3 3 3 3

The first sample case is valid for all subtasks. The second sample case is not valid for the first two subtasks, and valid for the remaining subtasks.

In the first sample case, we have no Tai and no Kshons, so we can't produce anything. (Alchemy is yet to discover how to produce something out of nothing.)

In the second sample case, we can produce four Aqua through the following process:

• Use one A -> * Kshon to convert one Aqua into one Breath.
• Use the B -> BB Kshon to convert the one Breath into two Breath.
• Use two B -> * Kshons to convert the two Breath into two Aqua.

The two Aqua in the last step, combined with the two remaining original Aqua, are four Aqua in total. There is one remaining A -> * Kshon that we did not use.

Similarly, this process produces three Dahnium:

• Use one A -> * Kshon to convert one Aqua into one Breath.
• Use the B -> BB Kshon to convert the one Breath into two Breath.
• Use one B -> * Kshon to convert one Breath into one Dahnium.
• Use the remaining A -> * Kshon to convert the remaining Aqua into one Dahnium.
• Use the remaining B -> * Kshon to convert the remaining Breath into one Dahnium.

At the end of the process, there is one Aqua and three Dahnium, but only the number of Dahnium matters. Similarly, we can produce three Breath, Copper, Earth, Fire, Gold, Hydrargyrum, Iron, and Jodium.

Note that the process "resets" for different Tai. Each process is independent of the other ones. It can also be shown that these are the maximum number of each Tai that can be made by any series of Kshons.