更好的阅读体验：https://blog.csdn.net/tenkuo/article/details/163430515?spm=1001.2014.3001.5501

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef __int128 i128;

const int N = 2000000 + 10;
const int M = 1 << 21;  // 2,097,152

// 三个NTT模数
const LL P1 = 998244353;
const LL P2 = 1004535809;
const LL P3 = 469762049;
const LL G = 3;

// 全局变量
int n, m;
int limit, l;
int r[M];

// 四个拆分段（每段16位）
LL A[4][M], B[4][M], C[M];
LL conv1[4][N], conv2[4][N], conv3[4][N];

// 快速幂
LL qpow(LL a, LL b, LL P) {
    LL res = 1;
    while (b) {
        if (b & 1) res = (i128)res * a % P;
        a = (i128)a * a % P;
        b >>= 1;
    }
    return res;
}

// NTT变换
void ntt(LL a[], int type, LL P) {
    for (int i = 0; i < limit; i++) {
        if (i < r[i]) swap(a[i], a[r[i]]);
    }
    
    for (int mid = 1; mid < limit; mid <<= 1) {
        LL Wn = qpow(G, (P - 1) / (mid << 1), P);
        if (type == -1) {
            Wn = qpow(Wn, P - 2, P);
        }
        
        for (int R = (mid << 1), j = 0; j < limit; j += R) {
            LL w = 1;
            for (int k = 0; k < mid; k++, w = (i128)w * Wn % P) {
                LL x = a[j + k];
                LL y = (i128)a[j + mid + k] * w % P;
                a[j + k] = (x + y) % P;
                a[j + mid + k] = (x - y + P) % P;
            }
        }
    }
    
    if (type == -1) {
        LL inv_limit = qpow(limit, P - 2, P);
        for (int i = 0; i < limit; i++) {
            a[i] = (i128)a[i] * inv_limit % P;
        }
    }
}

ULL aa[N], bb[N];

// 计算一个模数下的所有拆位卷积
void calc(LL res[4][N], LL P) {
    int result_len = n + m - 1;
    
    // 1. 拆分系数
    for (int p = 0; p < 4; p++) {
        for (int i = 0; i < limit; i++) {
            A[p][i] = 0;
            B[p][i] = 0;
        }
        
        for (int i = 0; i < n; i++) {
            A[p][i] = (aa[i] >> (16 * p)) & 0xFFFF;
        }
        for (int i = 0; i < m; i++) {
            B[p][i] = (bb[i] >> (16 * p)) & 0xFFFF;
        }
        
        ntt(A[p], 1, P);
        ntt(B[p], 1, P);
    }
    
    // 2. 初始化结果
    for (int t = 0; t < 4; t++) {
        for (int i = 0; i < result_len; i++) {
            res[t][i] = 0;
        }
    }
    
    // 3. 计算卷积（交叉相乘）
    for (int p = 0; p < 4; p++) {
        for (int q = 0; q < 4; q++) {
            if (p + q > 3) continue;
            
            // 点乘
            for (int i = 0; i < limit; i++) {
                C[i] = (i128)A[p][i] * B[q][i] % P;
            }
            
            // 逆变换
            ntt(C, -1, P);
            
            // 累加到结果
            for (int k = 0; k < result_len; k++) {
                res[p + q][k] = (res[p + q][k] + C[k]) % P;
            }
        }
    }
}

// 求逆元
LL inv(LL x, LL P) {
    return qpow(x, P - 2, P);
}

// CRT合并三个模数的结果
LL crt(LL r1, LL r2, LL r3) {
    LL k1 = (r2 - r1) % P2;
    if (k1 < 0) k1 += P2;
    k1 = (i128)k1 * inv(P1 % P2, P2) % P2;
    
    i128 x12 = (i128)r1 + (i128)P1 * k1;
    i128 P12 = (i128)P1 * P2;
    
    LL r3_mod = (LL)(x12 % P3);
    LL k2 = (r3 - r3_mod) % P3;
    if (k2 < 0) k2 += P3;
    k2 = (i128)k2 * inv((LL)(P12 % P3), P3) % P3;
    
    i128 x = x12 + P12 * k2;
    
    return (LL)x;
}

ULL ans[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) cin >> aa[i];
    for (int i = 0; i < m; i++) cin >> bb[i];
    
    limit = 1;
    l = 0;
    while (limit < n + m - 1) {
        limit <<= 1;
        l++;
    }
    
    for (int i = 0; i < limit; i++) {
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    }
    
    calc(conv1, P1);
    calc(conv2, P2);
    calc(conv3, P3);
    
    for (int k = 0; k < n + m - 1; k++) {
        ULL res = 0;
        for (int t = 0; t < 4; t++) {
            LL r1 = conv1[t][k];
            LL r2 = conv2[t][k];
            LL r3 = conv3[t][k];
            LL com = crt(r1, r2, r3);
            res += (ULL)com << (16 * t);
        }
        ans[k] = res;
    }
    
    for (int i = 0; i < n + m - 1; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
    
    return 0;
}