Clarke and chemistry

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Clarke is a patient with multiple personality disorder. One day, Clarke turned into a junior student and took a chemistry exam.
But he did not get full score in this exam. He checked his test paper and found a naive mistake, he was wrong with a simple chemical equation balancer.
He was unhappy and wanted to make a program to solve problems like this.
This chemical equation balancer follow the rules:
Two valences $A$ combined by $|A|$ elements and $B$ combined by $|B|$ elements.
We get a new valence $C$ by a combination reaction and the stoichiometric coefficient of $C$ is $1$. Please calculate the stoichiometric coefficient $a$ of $A$ and $b$ of $B$ that $aA + bB = C,\ \ a, b \in \text{N}^*$.

Input

The first line contains an integer $T(1 \le T \le 10)$, the number of test cases.
For each test case, the first line contains three integers $A, B, C(1 \le A, B, C \le 26)$, denotes $|A|, |B|, |C|$ respectively.
Then $A+B+C$ lines follow, each line looks like $X\ c$, denotes the number of element $X$ of $A, B, C$ respectively is $c$. ($X$ is one of $26$ capital letters, guarantee $X$ of one valence only appear one time, $1 \le c \le 100$)

Output

For each test case, if we can balance the equation, print $a$ and $b$. If there are multiple answers, print the smallest one, $a$ is smallest then $b$ is smallest. Otherwise print NO.

Sample Input

2 2 3 5 A 2 B 2 C 3 D 3 E 3 A 4 B 4 C 9 D 9 E 9 2 2 2 A 4 B 4 A 3 B 3 A 9 B 9

Sample Output

2 3 NO Hint: The first test case, $a=2, b=3$ can make equation right. The second test case, no any answer.

Hint

hujie

Source

BestCoder Round #72 (div.2)

提交代码