1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
typedef long long lnt;
const int N = 1 << 18;
const int P = (479 << 21) + 1;
const int g = 3;
int n, m, R[400005], L, mx;
int a[400005], b[400005], c[400005], _wn[400005], __wn[400005];
int ksm(lnt a, lnt b, lnt c) {
    lnt r = 1, t = a;
    while (b) {
        if (b & 1ll) r = (r * t) % c;
        t = (t * t) % c;
        b >>= 1ll;
    }
    return r;
}
void ntt(int *a, bool inv) {
    for (int i = 1; i < N; ++i) if (R[i] > i) swap(a[i], a[R[i]]);
    for (int i = 1; i < N; i <<= 1) {
        int wn = _wn[i];
        if (inv) wn = __wn[i];
        for (int j = 0; j < N; j += (i << 1)) {
            int w = 1;
            for (int k = 0; k < i; ++k) {
                int x = a[j + k], y = lnt(a[j + k + i]) * w % P;
                a[j + k] = (x + y) % P;
                a[j + k + i] = (x - y + P) % P;
                w = lnt(w) * wn % P;
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int j = 0; j <= m; ++j)
        scanf("%d", &b[j]);
    mx = n + m;
    L = 17;
    for (int i = 1; i < N; i <<= 1) {
        _wn[i] = ksm(g, (P-1)/(i<<1), P);
        __wn[i] = ksm(_wn[i], P-2, P);
    }
    for (int i = 1; i < N; ++i)
        R[i] = (R[i >> 1] >> 1) | ((i & 1) << L);
    ntt(a, false); ntt(b, false);
    for (int i = 0; i < N; ++i) c[i] = lnt(a[i]) * b[i] % P;
    ntt(c, true);
    for (int i = 0; i <= mx; ++i)
        printf("%d ", int(lnt(c[i]) * ksm(N, P-2, P) % P));
}