Problem:


Score : 100 points

Problem Statement

You are given two integer arrays a_0, a_1, ..., a_{N - 1} and b_0, b_1, ..., b_{M - 1}. Calculate the array c_0, c_1, ..., c_{(N - 1) + (M - 1)}, defined by c_i = \sum_{j = 0}^i a_j b_{i - j} \bmod 998244353.

Constraints

1 \leq N, M \leq 524288

0 \leq a_i, b_i < 998244353

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N M
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{M-1}

Output

Print the answer in the following format:

c_0 c_1 ... c_{(N - 1) + (M - 1)}

Sample Input 1

4 5
1 2 3 4
5 6 7 8 9

Sample Output 1

5 16 34 60 70 70 59 36

Sample Input 2

1 1
10000000
10000000

Sample Output 2

871938225



Sample input:
4 5
1 2 3 4
5 6 7 8 9


Sample output:
5 16 34 60 70 70 59 36

Submission status: Accepted

Solution code:
class Convolution():
    def __init__(self, mod):
        self.mod = mod
        self.root = self.primitive_root(mod)
        self.first1 = True
        self.first2 = True
        self.sum_e = [0] * 30
        self.sum_ie = [0] * 30

    def primitive_root(self, m):
        if m == 2: return 1
        if m == 167772161: return 3
        if m == 469762049: return 3
        if m == 754974721: return 11
        if m == 998244353: return 3
        divs = [0] * 20
        cnt = 1
        x = (m - 1) // 2
        while x % 2 == 0: x //= 2
        i = 3
        while i * i <= x:
            if x % i == 0:
                divs[cnt] = i
                cnt += 1
                while x % i == 0: x //= i
            i += 2
        if x > 1:
            divs[cnt] = x
            cnt += 1
        g = 2
        while True:
            for i in range(cnt):
                if pow(g, (m - 1) // divs[i], m) == 1: break
            else:
                return g
            g += 1

    def inv_gcd(self, a, b):
        a %= b
        if a == 0: return b, 0
        s = b
        t = a
        m0 = 0
        m1 = 1
        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u
            s, t = t, s
            m0, m1 = m1, m0
        if m0 < 0: m0 += b // s
        return s, m0

    def butterfly(self, arr):
        mod = self.mod
        g = self.root
        n = len(arr)
        h = (n - 1).bit_length()
        if self.first1:
            self.first1 = False
            es = [0] * 30
            ies = [0] * 30
            m = mod - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(g, m >> cnt2, mod)
            ie = pow(e, mod - 2, mod)
            for i in range(cnt2 - 1)[::-1]:
                es[i] = e
                ies[i] = ie
                e *= e
                e %= mod
                ie *= ie
                ie %= mod
            now = 1
            for i in range(cnt2 - 2):
                self.sum_e[i] = es[i] * now % mod
                now *= ies[i]
                now %= mod
        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p] * now
                    arr[i + offset] = (l + r) % mod
                    arr[i + offset + p] = (l - r) % mod
                now *= self.sum_e[(~s & -~s).bit_length() - 1]
                now %= mod

    def butterfly_inv(self, arr):
        mod = self.mod
        g = self.root
        n = len(arr)
        h = (n - 1).bit_length()
        if self.first2:
            self.first2 = False
            es = [0] * 30
            ies = [0] * 30
            m = mod - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(g, m >> cnt2, mod)
            ie = pow(e, mod - 2, mod)
            for i in range(cnt2 - 1)[::-1]:
                es[i] = e
                ies[i] = ie
                e *= e
                e %= mod
                ie *= ie
                ie %= mod
            now = 1
            for i in range(cnt2 - 2):
                self.sum_ie[i] = ies[i] * now % mod
                now *= es[i]
                now %= mod
        for ph in range(1, h + 1)[::-1]:
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p]
                    arr[i + offset] = (l + r) % mod
                    arr[i + offset + p] = (mod + l - r) * inow % mod
                inow *= self.sum_ie[(~s & -~s).bit_length() - 1]
                inow %= mod

    def convolution(self, a, b):
        mod = self.mod
        n = len(a)
        m = len(b)
        if not n or not m: return []
        if min(n, m) <= 50:
            if n < m:
                n, m = m, n
                a, b = b, a
            res = [0] * (n + m - 1)
            for i in range(n):
                for j in range(m):
                    res[i + j] += a[i] * b[j]
                    res[i + j] %= mod
            return res
        z = 1 << (n + m - 2).bit_length()
        a += [0] * (z - n)
        b += [0] * (z - m)
        self.butterfly(a)
        self.butterfly(b)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= mod
        self.butterfly_inv(a)
        a = a[:n + m - 1]
        iz = pow(z, mod - 2, mod)
        for i in range(n + m - 1):
            a[i] *= iz
            a[i] %= mod
        return a

    def convolution_ll(self, a, b):
        n = len(a)
        m = len(b)
        if not n or not m: return []
        mod1 = 754974721
        mod2 = 167772161
        mod3 = 469762049
        m2m3 = mod2 * mod3
        m1m3 = mod1 * mod3
        m1m2 = mod1 * mod2
        m1m2m3 = mod1 * mod2 * mod3
        i1 = self.inv_gcd(m2m3, mod1)[1]
        i2 = self.inv_gcd(m1m3, mod2)[1]
        i3 = self.inv_gcd(m1m2, mod3)[1]
        c1 = self.convolution(a.copy(), b.copy(), mod1)
        c2 = self.convolution(a.copy(), b.copy(), mod2)
        c3 = self.convolution(a.copy(), b.copy(), mod3)
        c = [0] * (n + m - 1)
        for i in range(n + m - 1):
            x = 0
            x += (c1[i] * i1) % mod1 * m2m3
            x += (c2[i] * i2) % mod2 * m1m3
            x += (c3[i] * i3) % mod3 * m1m2
            x %= m1m2m3
            c[i] = x
        return c

import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

cv = Convolution(998244353)

print(*cv.convolution(A, B))

Submission status: Accepted

Solution code:
class Convolution():
    def __init__(self, mod):
        self.mod = mod
        self.root = self.primitive_root(mod)
        self.first1 = True
        self.first2 = True
        self.sum_e = [0] * 30
        self.sum_ie = [0] * 30



    def primitive_root(self, m):
        if m == 2: return 1
        if m == 167772161: return 3
        if m == 469762049: return 3
        if m == 754974721: return 11
        if m == 998244353: return 3
        divs = [0] * 20
        cnt = 1
        x = (m - 1) // 2
        while x % 2 == 0:
            x //= 2
        i = 3
        while i * i <= x:
            if x % i == 0:
                divs[cnt] = i
                cnt += 1
                while x % i == 0:
                    x //= i
            i += 2
        if x > 1:
            divs[cnt] = x
            cnt += 1
        g = 2
        while True:
            for i in range(cnt):
                if pow(g, (m - 1) // divs[i], m) == 1:
                    break
            else:
                return g
            g += 1

    def inv_gcd(self, a, b):
        a %= b
        if a == 0: return b, 0
        s = b
        t = a
        m0 = 0
        m1 = 1
        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u
            s, t = t, s
            m0, m1 = m1, m0
        if m0 < 0: m0 += b // s
        return s, m0

    def butterfly(self, arr):
        mod = self.mod
        g = self.root
        n = len(arr)
        h = (n - 1).bit_length()
        if self.first1:
            self.first1 = False
            es = [0] * 30
            ies = [0] * 30
            m = mod - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(g, m >> cnt2, mod)
            ie = pow(e, mod - 2, mod)
            for i in range(cnt2 - 1)[::-1]:
                es[i] = e
                ies[i] = ie
                e *= e
                e %= mod
                ie *= ie
                ie %= mod
            now = 1
            for i in range(cnt2 - 2):
                self.sum_e[i] = es[i] * now % mod
                now *= ies[i]
                now %= mod
        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p] * now
                    arr[i + offset] = (l + r) % mod
                    arr[i + offset + p] = (l - r) % mod
                now *= self.sum_e[(~s & -~s).bit_length() - 1]
                now %= mod

    def butterfly_inv(self, arr):
        mod = self.mod
        g = self.root
        n = len(arr)
        h = (n - 1).bit_length()
        if self.first2:
            self.first2 = False
            es = [0] * 30
            ies = [0] * 30
            m = mod - 1
            cnt2 = (m & -m).bit_length() - 1
            e = pow(g, m >> cnt2, mod)
            ie = pow(e, mod - 2, mod)
            for i in range(cnt2 - 1)[::-1]:
                es[i] = e
                ies[i] = ie
                e *= e
                e %= mod
                ie *= ie
                ie %= mod
            now = 1
            for i in range(cnt2 - 2):
                self.sum_ie[i] = ies[i] * now % mod
                now *= es[i]
                now %= mod
        for ph in range(1, h + 1)[::-1]:
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p]
                    arr[i + offset] = (l + r) % mod
                    arr[i + offset + p] = (mod + l - r) * inow % mod
                inow *= self.sum_ie[(~s & -~s).bit_length() - 1]
                inow %= mod

    def convolution(self, a, b):
        mod = self.mod
        n = len(a)
        m = len(b)
        if not n or not m: return []
        if min(n, m) <= 50:
            if n < m:
                n, m = m, n
                a, b = b, a
            res = [0] * (n + m - 1)
            for i in range(n):
                for j in range(m):
                    res[i + j] += a[i] * b[j]
                    res[i + j] %= mod
            return res
        z = 1 << (n + m - 2).bit_length()
        a += [0] * (z - n)
        b += [0] * (z - m)
        self.butterfly(a)
        self.butterfly(b)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= mod
        self.butterfly_inv(a)
        a = a[:n + m - 1]
        iz = pow(z, mod - 2, mod)
        for i in range(n + m - 1):
            a[i] *= iz
            a[i] %= mod
        return a

    def convolution_ll(self, a, b):
        n = len(a)
        m = len(b)
        if not n or not m: return []
        mod1 = 754974721
        mod2 = 167772161
        mod3 = 469762049
        m2m3 = mod2 * mod3
        m1m3 = mod1 * mod3
        m1m2 = mod1 * mod2
        m1m2m3 = mod1 * mod2 * mod3
        i1 = self.inv_gcd(m2m3, mod1)[1]
        i2 = self.inv_gcd(m1m3, mod2)[1]
        i3 = self.inv_gcd(m1m2, mod3)[1]
        c1 = self.convolution(a.copy(), b.copy(), mod1)
        c2 = self.convolution(a.copy(), b.copy(), mod2)
        c3 = self.convolution(a.copy(), b.copy(), mod3)
        c = [0] * (n + m - 1)
        for i in range(n + m - 1):
            x = 0
            x += (c1[i] * i1) % mod1 * m2m3
            x += (c2[i] * i2) % mod2 * m1m3
            x += (c3[i] * i3) % mod3 * m1m2
            x %= m1m2m3
            c[i] = x
        return c

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

cv = Convolution(998244353)

print(*cv.convolution(A, B))

Submission status: Accepted

Solution code:

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libc.stdio cimport getchar, printf
from libcpp.vector cimport vector

cdef extern from *:
    ctypedef int MOD_t "998244353"
    ctypedef long long ll "long long"

cdef extern from "<atcoder/convolution>" namespace "atcoder":
    vector[int] convolution[M](vector[int] a, vector[int] b)
    vector[ll] convolution_ll(vector[ll] a, vector[ll] b)

cpdef vector[int] Conv(vector[int] a, vector[int] b):
    return convolution[MOD_t](a, b)

cpdef vector[ll] ConvL(vector[ll] a, vector[ll] b):
    return convolution_ll(a, b)

cdef inline vector[int] readint(int n) nogil:
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef vector[int] readInt(int n):
    return readint(n)

cdef inline void printlongn(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef void printLongN(vector[long] l, int n):
    printlongn(l, n)

cdef inline void printlong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])

cpdef void printLong(vector[long] l, int n):
    printlong(l, n)
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import Conv, readInt, printLong

N,M = readInt(2)

A = readInt(N)
B = readInt(M)

C = Conv(A,B)

printLong(C, len(C))

Submission status: Accepted

Solution code:
class Ntt:
    def __init__(self, mod=10**9+7, root=3):
        self.mod = mod
        self.roots = [pow(root, (mod - 1) >> i, mod) for i in range(24)]
        self.iroots = [pow(x, mod - 2, mod) for x in self.roots]
        
    def untt(self, a, n):
        for i in range(n):
            m = 1 << (n - i - 1)
            for s in range(1 << i):
                wn = 1
                s *= m * 2
                for p in range(m):
                    a[s + p], a[s + p + m] = (a[s + p] + a[s + p + m]) % self.mod,\
                                             (a[s + p] - a[s + p + m]) * wn % self.mod
                    wn = wn * self.roots[n - i] % self.mod
    
    def iuntt(self, a, n):
        for i in range(n):
            m = 1 << i
            for s in range(1 << (n - i - 1)):
                wn = 1
                s *= m * 2
                for p in range(m):
                    a[s + p], a[s + p + m] = (a[s + p] + a[s + p + m] * wn) % self.mod,\
                                             (a[s + p] - a[s + p + m] * wn) % self.mod
                    wn = wn * self.iroots[i + 1] % self.mod
    
        inv = pow((self.mod + 1) // 2, n, self.mod)
        for i in range(1 << n):
            a[i] = a[i] * inv % self.mod
    
    def convolution(self, a, b):
        deg = len(a) + len(b) - 2
        n = deg.bit_length()
        N = 1 << n
        a += [0] * (N - len(a))
        b += [0] * (N - len(b))
        self.untt(a, n)
        self.untt(b, n)
        for i in range(N):
            a[i] = a[i] * b[i] % self.mod
        self.iuntt(a, n)
        return a[:deg + 1]


N, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mod = 998244353

ntt = Ntt(mod=mod)
print(*ntt.convolution(a, b))

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include,/opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector

cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    cpdef int merge(self,a,b): return self.ptr.merge(a,b)
    cpdef bool same(self,a,b): return self.ptr.same(a,b)
    cpdef int leader(self,a): return self.ptr.leader(a)
    cpdef int size(self,a): return self.ptr.size(a)
    cpdef vector[vector[int]] groups(self): return self.ptr.groups()

cdef extern from "<atcoder/fenwicktree>" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree()
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)
cdef class fenwick_tree_:
    cdef fenwick_tree[int] *ptr
    def __cinit__(self, int n): self.ptr = new fenwick_tree[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef void add(self, int p, long x): self.ptr.add(p, x)
    cpdef long sum(self, int l, int r): return self.ptr.sum(l, r)

cdef extern from "<atcoder/string>" namespace "atcoder":
    vector[int] suffix_array(vector[int] s, int upper)
    vector[int] suffix_array(vector[long] s)
    vector[int] suffix_array(string s)
    vector[int] lcp_array(vector[long] s, vector[int] sa)
    vector[int] lcp_array(string s, vector[int] sa)
    vector[int] z_algorithm(vector[long] s)
    vector[int] z_algorithm(string s)
cpdef vector[int] suffix_array_u(vector[int] s, int upper): return suffix_array(s, upper)
cpdef vector[int] suffix_array_l(vector[long] s): return suffix_array(s)
cpdef vector[int] suffix_array_s(string s): return suffix_array(s)
cpdef vector[int] lcp_array_l(vector[long] s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] lcp_array_s(string s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] z_algorithm_l(vector[long] s): return z_algorithm(s)
cpdef vector[int] z_algorithm_s(string s): return z_algorithm(s)

cdef extern from "<atcoder/maxflow>" namespace "atcoder":
    cdef cppclass mf_graph[Cap]:
        mf_graph(int n)
        int add_edge(int frm, int to, Cap cap)
        Cap flow(int s, int t)
        Cap flow(int s, int t, Cap flow_limit)
        vector[bool] min_cut(int s)
        cppclass edge:
            int frm "from", to
            Cap cap, flow
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
        void change_edge(int i, Cap new_cap, Cap new_flow)
cdef class mf_graph_:
    cdef mf_graph[int] *ptr
    def __cinit__(self, int n): self.ptr = new mf_graph[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, int cap): return self.ptr.add_edge(frm, to, cap)
    cpdef int flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef int flow_limit(self, int s, int t, int flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[bool] min_cut(self, int s): return self.ptr.min_cut(s)
    cpdef vector[int] get_edge(self, int i):
        cdef mf_graph[int].edge *e = new mf_graph[int].edge(self.ptr.get_edge(i))
        cdef vector[int] *ret_e = new vector[int]()        
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        return ret_e[0]
    cpdef vector[vector[int]] edges(self):
        cdef vector[mf_graph[int].edge] es = self.ptr.edges()
        cdef vector[vector[int]] *ret_es = new vector[vector[int]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
        return ret_es[0]
    cpdef void change_edge(self, int i, int new_cap, int new_flow): self.ptr.change_edge(i, new_cap, new_flow)

cdef extern from *:
    ctypedef int MOD "998244353"
    ctypedef long long ll "long long"
cdef extern from "<atcoder/convolution>" namespace "atcoder":
    vector[int] convolution[m](vector[int] a, vector[int] b)
    vector[ll] convolution_ll(vector[ll] a, vector[ll] b)
cpdef convolution_(vector[int] a, vector[int] b): return convolution[MOD](a, b)
cpdef convolution_ll_(vector[ll] a, vector[ll] b): return convolution_ll(a, b)
"""

import os
try:
    from atcoder import *
except:
    open('atcoder.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
print(*convolution_(A,B))

Submission status: Accepted

Solution code:
import numpy as np
from numpy.fft import rfft,irfft

# 参考: https://atcoder.jp/contests/practice2/submissions/16645527

def convolve(a1,a2):
    n = 2**(len(a1)+len(a2)+1).bit_length()
    b1,b2=np.zeros(n),np.zeros(n)
    b1[:len(a1)], b2[:len(a2)]= a1,a2
    return (irfft(rfft(b1)*rfft(b2))+0.5).astype(int)
  
def convolve_large(a,b,mod):
    d = 1<<10
    a1, a2 = np.divmod(a,d*d)
    a2, a3 = np.divmod(a2,d)
    b1, b2 = np.divmod(b,d*d)
    b2, b3 = np.divmod(b2,d)
    aa = convolve(a1,b1) % mod
    bb = convolve(a2,b2) % mod
    cc = convolve(a3,b3) % mod
    dd = (convolve(a1+a2, b1+b2) - (aa+bb)) % mod
    ee = (convolve(a2+a3, b2+b3) - (bb+cc)) % mod
    ff = (convolve(a1+a3, b1+b3) - (aa+cc)) % mod
    h = (((aa*d*d) % mod)*d*d + ((dd*d*d) % mod)*d + (bb+ff)*d*d + ee*d + cc) % mod
    return h


def main():
  N,M=map(int,input().split())
  *A,=map(int,input().split())
  *B,=map(int,input().split())
  mod = 998244353

  print(*convolve_large(A,B,mod)[:N+M-1])
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/atcoder-stl
from libcpp.vector cimport vector
cdef extern from *:
    ctypedef int MOD_t "998244353"
    ctypedef long long ll "long long"
cdef extern from "<atcoder/convolution>" namespace "atcoder" nogil:
    vector[int] convolution[M](vector[int] a, vector[int] b)
    #vector[long] convolution[M](vector[long] a, vector[long] b)
    #vector[ll] convolution[M](vector[ll] a, vector[ll] b)
    vector[ll] convolution_ll(vector[ll] a, vector[ll] b)
from libc.stdio cimport getchar, printf
cdef inline int read() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: return c
        c = c * 10 + b
cdef int n = read(), m = read(), i
cdef vector[int] a = vector[int](n), b = vector[int](m)
for i in range(n): a[i] = read()
for i in range(m): b[i] = read()
cdef vector[int] c = convolution[MOD_t](a, b)
for i in range(n + m - 1): printf('%d ', c[i])
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
def primitive_root(m):
    if m == 2: return 1
    if m == 167772161: return 3
    if m == 469762049: return 3
    if m == 754974721: return 11
    if m == 998244353: return 3
    divs = [0] * 20
    cnt = 1
    x = (m - 1) // 2
    while x % 2 == 0:
        x //= 2
    i = 3
    while i * i <= x:
        if x % i == 0:
            divs[cnt] = i
            cnt += 1
            while x % i == 0:
                x //= i
        i += 2
    if x > 1:
        divs[cnt] = x
        cnt += 1
        g = 2
    while True:
        ok = True
        for i in range(cnt):
            if pow(g, (m - 1) // divs[i], m) == 1:
                ok = False
                break
        if ok:
            return g
        g += 1

def inv_gcd(a, b):
    a %= b
    if a == 0: return b, 0
    s = b
    t = a
    m0 = 0
    m1 = 1
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
        s, t = t, s
        m0, m1 = m1, m0
    if m0 < 0: m0 += b // s
    return s, m0

def butterfly(arr, mod):
    g = primitive_root(mod)
    n = len(arr)
    h = (n - 1).bit_length()
    first = True
    sum_e = [0] * 30
    if first:
        first = False
        es = [0] * 30
        ies = [0] * 30
        m = mod - 1
        cnt2 = (m & -m).bit_length() - 1
        e = pow(g, m >> cnt2, mod)
        ie = pow(e, mod - 2, mod)
        for i in range(cnt2 - 1)[::-1]:
            es[i] = e
            ies[i] = ie
            e *= e
            e %= mod
            ie *= ie
            ie %= mod
        now = 1
        for i in range(cnt2 - 2):
            sum_e[i] = es[i] * now % mod
            now *= ies[i]
            now %= mod
    for ph in range(1, h + 1):
        w = 1 << (ph - 1)
        p = 1 << (h - ph)
        now = 1
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = arr[i + offset]
                r = arr[i + offset + p] * now
                arr[i + offset] = (l + r) % mod
                arr[i + offset + p] = (l - r) % mod
            now *= sum_e[(~s & -~s).bit_length() - 1]
            now %= mod

def butterfly_inv(arr, mod):
    g = primitive_root(mod)
    n = len(arr)
    h = (n - 1).bit_length()
    first = True
    sum_ie = [0] * 30
    if first:
        first = False
        es = [0] * 30
        ies = [0] * 30
        m = mod - 1
        cnt2 = (m & -m).bit_length() - 1
        e = pow(g, m >> cnt2, mod)
        ie = pow(e, mod - 2, mod)
        for i in range(cnt2 - 1)[::-1]:
            es[i] = e
            ies[i] = ie
            e *= e
            e %= mod
            ie *= ie
            ie %= mod
        now = 1
        for i in range(cnt2 - 2):
            sum_ie[i] = ies[i] * now % mod
            now *= es[i]
            now %= mod
    for ph in range(1, h + 1)[::-1]:
        w = 1 << (ph - 1)
        p = 1 << (h - ph)
        inow = 1
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = arr[i + offset]
                r = arr[i + offset + p]
                arr[i + offset] = (l + r) % mod
                arr[i + offset + p] = (mod + l - r) * inow % mod
            inow *= sum_ie[(~s & -~s).bit_length() - 1]
            inow %= mod

def convolution(a, b, mod=998244353):
    n = len(a)
    m = len(b)
    if not n or not m: return []
    if min(n, m) <= 60:
        if n < m:
            n, m = m, n
            a, b = b, a
        res = [0] * (n + m - 1)
        for i in range(n):
            for j in range(m):
                res[i + j] += a[i] * b[j]
                res[i + j] %= mod
        return res
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    b += [0] * (z - m)
    butterfly(a, mod)
    butterfly(b, mod)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= mod
    butterfly_inv(a, mod)
    a = a[:n + m - 1]
    iz = pow(z, mod - 2, mod)
    for i in range(n + m - 1):
        a[i] *= iz
        a[i] %= mod
    return a

def convolution_ll(a, b):
    n = len(a)
    m = len(b)
    if not n or not m: return []
    mod1 = 754974721
    mod2 = 167772161
    mod3 = 469762049
    m2m3 = mod2 * mod3
    m1m3 = mod1 * mod3
    m1m2 = mod1 * mod2
    m1m2m3 = mod1 * mod2 * mod3
    i1 = inv_gcd(m2m3, mod1)[1]
    i2 = inv_gcd(m1m3, mod2)[1]
    i3 = inv_gcd(m1m2, mod3)[1]
    c1 = convolution(a.copy(), b.copy(), mod1)
    c2 = convolution(a.copy(), b.copy(), mod2)
    c3 = convolution(a.copy(), b.copy(), mod3)
    c = [0] * (n + m - 1)
    for i in range(n + m - 1):
        x = 0
        x += (c1[i] * i1) % mod1 * m2m3
        x += (c2[i] * i2) % mod2 * m1m3
        x += (c3[i] * i3) % mod3 * m1m2
        x %= m1m2m3
        c[i] = x
    return c

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

print(*convolution(A, B))