Not a Convolution

Limits: 2 sec., 256 MiB

You’re given an array \(a\) of \(n\) integers and an array \(b\) of \(m\) integers.

Also there is an array \(c\) of \(n+m\) elements all of which initially are zeroes.

Arrays are indexed from 1.

The following code is executed:

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            c[i + gcd(i, j)] += a[i] * b[j]

\(\gcd(i, j)\) is the greatest common divisor of \(i\) and \(j\).

No integer overflows happen during the execution.

Find array \(c\) after the execution of the code.

Input

The first line contains an integer \(n\) — number of elements in the array \(a\).

The second line contains \(n\) integers — elements of the array \(a\).

The third line contains an integer \(m\) — number of elements in the array \(b\).

The fourth line contains \(m\) integers — elements of the array \(b\).

Output

In the single line print \(n+m\) integers — elements of the array \(c\).

Constraints

\(1 \le n, m \le 10^5\),

\(0 \le a_i, b_j \le 10^4\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 1 2 3 4 2 5 3 1	0 11 10 36 0 9 0