Description

A polynomial is an expression consisting of variables and coefficients, of the form:

$P(x) = c_k x^{e_k} + c_{k-1} x^{e_{k-1}} + \dots + c_1 x^{e_1} + c_0 x^{e_0}$.

In this problem, you are given two polynomials, $P_1(x)$ and $P_2(x)$. Your task is to compute their sum, $P_{sum}(x) = P_1(x) + P_2(x)$.

The rules for addition are as follows:

• When adding terms with the same exponent, their coefficients are summed up.
• If the sum of coefficients for a term results in zero, that term should be omitted from the final polynomial.
• The terms in the resulting polynomial must be ordered by exponent in descending order.

Format

Input

The input consists of five lines:

1. The first line contains two integers, $m$ and $n$, representing the number of terms in $P_1(x)$ and $P_2(x)$ respectively.
2. The next two lines describe $P_1(x)$:
   • One line for the coefficients
   • One line for the corresponding exponents
3. The following two lines describe $P_2(x)$ in the same format.

• $1 \leq m, n \leq 2 \times 10^5$
• Coefficients $c_i$ are integers: $-10^9 \leq c_i \leq 10^9$
• Exponents $e_i$ are non-negative integers: $0 \leq e_i \leq 10^9$
• Within each polynomial:
  • All exponents are unique
  • Terms are given in descending order of exponents

Output

Output two lines representing the sum polynomial $P_{sum}(x)$.

• The first line must contain the coefficients.
• The second line must contain the corresponding exponents.
• The terms must be given in descending order of exponents.
• If the resulting polynomial is zero (i.e., it has no terms), output two empty lines.

Hint

Online interactive guide to the code framework.

Samples

3 3
5 -2 1
3 1 0
-3 4 2
3 2 1

2 4 1
3 2 0

Explanation:

$P_1(x) = 5x^3 - 2x^1 + 1x^0$

$P_2(x) = -3x^3 + 4x^2 + 2x^1$

$P_{sum}(x) = (5-3)x^3 + 4x^2 + (-2+2)x^1 + 1x^0 = 2x^3 + 4x^2 + 1x^0$

Limitation

1s, 256MiB for each test case.