Не згортка

Обмеження: 2 сек., 256 МіБ

Задано масив $a$ з $n$ цілих чисел та масив $b$ з $m$ цілих чисел.

Також є масив $c$ з $n+m$ елементів, які початково нулі.

Масиви індексуються з 1.

Виконується такий код:

    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)$ — найбільший спільний дільник $i$ та $j$.

Під час виконання не відбувається жодних цілочислових переповнень.

Знайдіть масив $c$ після виконання коду.

Вхідні дані

У першому рядку задано ціле число $n$ — кількість елементів у масиві $a$.

Другий рядок містить $n$ цілих чисел — елементи масиву $a$.

У третьому рядку задано ціле число $m$ — кількість елементів у масиві $b$.

Четвертий рядок містить $m$ цілих чисел — елементи масиву $b$.

Вихідні дані

У єдиному рядку виведіть $n + m$ цілих чисел — елементи масиву $c$.

Обмеження

$1 \le n, m \le 10^5$,

$0 \le a_i, b_j \le 10^4$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 1 2 3 4 2 5 3 1	0 11 10 36 0 9 0