Consider the following magical program: (all array indices are 0-based, all division results are integers truncated towards 0)

Define arrays a[], b[], c[]
Define function Magic(x, y, z):
{
    If length of a == z:
        Return x >= y
    If x % a[z] < y % a[z]:
        Return False
    Return Magic(x / a[z], y / a[z], z + 1)
}
Define function Main():
{
    Read a[], b[]
    Let length of c[] be the same as b[], and initialize all elements of c[] to 0
    For i from 0 to length of b - 1:
        For j from 0 to i:
            If Magic(i, j, 0):
                c[i] += b[j]
    Output a[], c[]
}

This program is currently very inefficient (the time complexity is clearly at least quadratic) and cannot handle calculations on the order of millions quickly, but our task now is not just to optimize it.

We are given the output of this program, and you need to act as a "non-deterministic machine" to provide a possible input.

Please pay attention to the memory limits of this problem.

Input

The first line contains the length of $a$. The second line contains space-separated positive integers representing the elements of $a$ in order.

The third line contains the length of $c$. The fourth line contains space-separated integers representing the elements of $c$ in order.

Adjacent numbers on each line are separated by exactly one space.

The length of $a$ will not exceed $10^4$. Each element of $a$ will not exceed $10^9$.

The length of $c$ will not exceed $10^6$. There is no direct guarantee on the range of elements in $c$, but it is guaranteed that there exists a solution $b$ such that the absolute value of each element of $b$ does not exceed $10^9$.

Both $a$ and $c$ have at least one element.

Output

The first line outputs the length of $a$. The second line outputs space-separated positive integers representing the elements of $a$ in order.

The third line outputs the length of $b$. The fourth line outputs space-separated integers representing the elements of $b$ in order.

Adjacent numbers on each line are separated by exactly one space.

You must ensure that the absolute value of each element of your output $b$ does not exceed $10^9$. It is guaranteed that a feasible solution satisfying this condition exists. If there are multiple feasible solutions, you may output any one of them.

Examples

Input 1

3
2 3 3
10
1 0 2 9 3 8 4 7 5 6

Output 1

3
2 3 3
10
1 -1 1 8 1 -2 3 4 0 -10

Subtasks

This problem is divided into several subtasks, but does not use bundled testing. Each subtask contains several test cases; you will receive points for a test case if your output for that test case is correct. The score for a subtask is the sum of the scores of its individual test cases.

Let $n$ be the length of $c$ and $m$ be the length of $a$:

Subtask 1 (4 points)

$n = 1$, $m \leq 100$.

Subtask 2 (22 points)

$n \leq 100$, $m \leq 100$.

Subtask 3 (6 points)

$n \leq 1000$, $m \leq 1000$.

Subtask 4 (8 points)

$n \leq 10^4$.

Subtask 5 (21 points)

$n = 2^m$, all elements in $a$ are $2$.

Subtask 6 (9 points)

All elements in $a$ are $2$.

Subtask 7 (7 points)

$m = 1$.

Subtask 8 (12 points)

$m \leq 20$.

Subtask 9 (11 points)

No special constraints.