Problem C: Wtd attacks wtc

Problem C: Wtd attacks wtc

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2090  Solved: 259
[Submit][Status][Web Board]

Description

Wtd's army attacks wtc’s castle several times. However, wtc always wins these wars. Then, wtd wants to know the combat values of among different soldiers.

The total combat values of soldiers in this planet is defined as addition among two polynomials. Wtd asks you for help as he is not good at math. Each time, wtd will give you the (coefficient, exponent) pairs (These pairs will be given by in ascending order of exponent) of two polynomials. For example, will be given as (1 0), (2 1), (3 2). You return the polynomial after addition to him. Since the soldiers may be injured in the war, so the coefficients could be negative values.

Note that, to help army master to understand:

Please pay attention to the special cases, e.g., the result is 0, the sum of compact values is 0 or 1 at level i. We follow all these definitions and notations in Math.

Input

First line will be a positive integer T (T<=100), which is the number of messages.

The first line will be an integer n, which is the number of terms of the first polynomial. Then n lines will be the coefficients and exponents of the terms.

After n + 1 lines, there will be an integer m for the number of terms of the second polynomial. And m lines of (coefficient, exponent) pairs.

(0 <= n, m <= 1000, all exponents are in the range [0, 109], all coefficients are in the range [-10000, 10000])

Output

For each message, print the polynomial with the same syntax as the sample shows.

Sample Input

1
2
2 2
3 3
2
1 2
2 4

Sample Output

3x^2+3x^3+2x^4

HINT

[Submit][Status]