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.