Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2858

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Mr Keniess was very rich and he stored his most valuable diamond in a strongbox. The strongbox can be opened with a password made up of digital string. Mr Keniess set the password a very big number, and he remembered it by an equation "A+B=C". Since A, B and C are very big numbers, he remembered them by module equations. Now the famous theif Kid got the equations. But he could not got the password himself. He asked you, his most helpful assistant that knows computer very well, for help.


The first line of each test case contains 3 integers N, M, P. Then N lines describe A, M lines describe B, and P lines describe C. The N + M + P lines each contains two integers D and R, 0 <= R < D, indicates the coresponding integer when divided by D, the remainder is R.


Output -1 if there may be confliction with the data Kid got. Or output the equation inthe form of "A+B=C" in one line. There may be sveral solutions. Output the one with A minimum. If there still is a tie, choose the one with B minimum.

Sample Input

1 1 1
2 0
3 0
6 5

Sample Output


Author: GUAN, Yao
Source: ZOJ Monthly, June 2007
Submit    Status