Не згортка

Обмеження: 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