14981498 SUSTech Online Judge
Problem 1498 --Polynomial Summation

1498: Polynomial Summation

Time Limit: 2 Sec  Memory Limit: 512 MB
Submit: 1560  Solved: 334
[Submit][Status][Web Board]


Given two polynomials with n and m terms, please calculate the sum of the two polynomials.

Inputs and outputs are exponentially smaller to larger

You must use your self-implemented linkedlist to solve this problem.


The first line has two numbers: n and m (0<n,m<1000000)

The next n lines are the coefficients and exponents of the terms in the first polynomial.

After that, the next m lines, are the coefficients and exponents of the terms in the second polynomial.

The values of all coefficients and exponents are in the range (-1e9,1e9)


The first line is an integer k, it is the number of terms in the result.

The next k lines are the coefficients and exponents of the result.

If the coefficient of the item is 0, you should not count it as result.

Sample Input

2 2
2 1
1 3
2 3
1 4

Sample Output

2 1
3 3
1 4


Please use fast I/O.