In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
To open sesame one needs a set of tokens containing at least gold tokens, silver tokens and copper tokens. Initially, Ali Baba has at his disposal a certain number of tokens of each kind. He can exchange them with the Guardian of sesame, according to given rules. Every rule is of the form:
Such a rule denotes that Ali Baba can exchange gold tokens, silver tokens and copper tokens for gold tokens, silver tokens and copper tokens. Tokens received in a transaction can be exchanged in the next transactions.
Write a program that:
In the first line of the standard input there is one positive integer (, which is the number of sets of data. Then the sets of data follow. Each set of data consists of many lines.
In the first line there are three non-negative integers . They are the numbers of gold, silver and copper tokens respectively, owned by Ali Baba initially. In the second line there are three integers . They are the numbers of gold, silver and copper tokens needed to open sesame. In the third line there is written the number of rules , .
In each of the following lines there is a sequence of six numbers from the set . They describe a single rule: .
The numbers in each line are separated by single spaces.
In the -th line of the standard output there should be written the result for the -th set of data:
For the input data:
2 2 2 2 3 3 3 3 0 1 1 2 0 0 1 0 1 0 2 0 1 1 0 0 0 2 1 1 1 2 2 2 4 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 2 0 0 0 2 2
the correct result is:
Task author: Piotr Chrzastowski-Wachtel.