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

Solution (Python):
p, g = 998244353, 3
invg = pow(g, p-2, p)
W = [pow(g, (p - 1) >> i, p) for i in range(24)]
iW = [pow(invg, (p - 1) >> i, p) for i in range(24)]

def fft(k, f):
    for l in range(k)[::-1]:
        d = 1 << l
        u = 1
        for i in range(d):
            for j in range(i, 1 << k, 2*d):
                f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
            u = u * W[l+1] % p

def ifft(k, f):
    for l in range(k):
        d = 1 << l
        u = 1
        for i in range(d):
            for j in range(i, 1 << k, 2*d):
                f[j+d] *= u
                f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
            u = u * iW[l+1] % p

def convolve(a, b):
    n0 = len(a) + len(b) - 1
    k = (n0).bit_length() + 1
    n = 1 << k
    a = a + [0] * (n - len(a))
    b = b + [0] * (n - len(b))
    fft(k, a), fft(k, b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(k, a)
    invn = pow(n, p - 2, p)
    for i in range(n0):
        a[i] = a[i] * invn % p
    return a[:n0]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):
p, g = 998244353, 3
invg = pow(g, p-2, p)
W = [pow(g, (p - 1) >> i, p) for i in range(24)]
iW = [pow(invg, (p - 1) >> i, p) for i in range(24)]

def fft(k, f):
    for l in range(k)[::-1]:
        d = 1 << l
        u = 1
        for i in range(d):
            for j in range(i, 1 << k, 2*d):
                f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
            u = u * W[l+1] % p

def ifft(k, f):
    for l in range(k):
        d = 1 << l
        u = 1
        for i in range(d):
            for j in range(i, 1 << k, 2*d):
                f[j+d] *= u
                f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
            u = u * iW[l+1] % p

def convolve(a, b):
    n0, n1 = len(a), len(b)
    k = (max(n0, n1) - 1).bit_length() + 1
    n = 1 << k
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    fft(k, a), fft(k, b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(k, a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):
p, g = 998244353, 3
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):
p, g = 998244353, 3
def convolve(a, b):
    def fft(f):
        for l in range(k)[::-1]:
            d = 1 << l
            v = W[k-1-l]
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p

    def ifft(f):
        for l in range(k):
            d = 1 << l
            v = iW[k-1-l]
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
 
    n0, n1 = len(a), len(b)
    k = (n0 + n1 - 1).bit_length()
    n = 1 << k
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    W = [w]
    for i in range(k):
        W.append(W[-1] ** 2 % p)
    invw = pow(w, p-2, p)
    iW = [invw]
    for i in range(k):
        iW.append(iW[-1] ** 2 % p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):
p, g = 998244353, 3
invg = pow(g, p-2, p)
W = [pow(g, (p - 1) >> i, p) for i in range(24)]
iW = [pow(invg, (p - 1) >> i, p) for i in range(24)]
def convolve(a, b):
    def fft(f):
        for l in range(k)[::-1]:
            d = 1 << l
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * W[l+1] % p

    def ifft(f):
        for l in range(k):
            d = 1 << l
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * iW[l+1] % p

    n0, n1 = len(a), len(b)
    k = (max(n0, n1) - 1).bit_length() + 1
    n = 1 << k
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):
p, g = 998244353, 3
invg = pow(g, p-2, p)
W = [pow(g, (p - 1) >> i, p) for i in range(24)]
iW = [pow(invg, (p - 1) >> i, p) for i in range(24)]
def convolve(a, b):
    def fft(f):
        for l in range(k)[::-1]:
            d = 1 << l
            v = W[l+1]
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p

    def ifft(f):
        for l in range(k):
            d = 1 << l
            v = iW[l+1]
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p

    n0, n1 = len(a), len(b)
    k = (max(n0, n1) - 1).bit_length() + 1
    n = 1 << k
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
MOD = 998244353

class Convolution:
    def __init__(self):
        pass

    def _ceil_pow2(self, n):
        assert n >= 0
        x = 0
        while (1<<x) < n:
            x += 1
        return x

    def _bsf(self, n):
        assert n >= 1
        return len(bin(n & -n)) - 3

    def _butterfly(self,a,mod):
        n = len(a)
        h = self._ceil_pow2(n)
        self.sum_e = [0] * 30
        es = [0] * 30
        ies = [0] * 30
        cnt2 = self._bsf(mod - 1)
        g = 3 
        e = pow(g, (mod-1)>>cnt2, mod)
        ie = pow(e,mod-2,mod)
        for i in range(cnt2,1,-1):
            es[i-2] = e
            ies[i-2] = 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 = a[i + offset]
                    r = a[i + offset + p] * now
                    a[i + offset] = (l+r) % mod
                    a[i + offset + p] = (l-r) % mod
                now *= self.sum_e[self._bsf(((1<<32)-1)^s)]
                now %= mod

    def _butterfly_inv(self,a,mod):
        n = len(a)
        h = self._ceil_pow2(n)
        self.sum_ie = [0] * 30
        es = [0] * 30
        ies = [0] * 30
        cnt2 = self._bsf(mod - 1)
        g = 3 
        e = pow(g, (mod-1)>>cnt2, mod)
        ie = pow(e,mod-2,mod)
        for i in range(cnt2,1,-1):
            es[i-2] = e
            ies[i-2] = 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(h,0,-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 = a[i + offset]
                    r = a[i + offset + p]
                    a[i + offset] = (l+r) % mod
                    a[i + offset + p] = ((l-r) * inow) % mod
                inow *= self.sum_ie[self._bsf(((1<<32)-1)^s)]
                inow %= mod

    def convolution_mod(self, a, b, mod):
        n,m = len(a),len(b)
        if n==0 or m==0: return []
        if min(n,m) <= 60:
            if n < m:
                a,b,n,m = b,a,m,n
            ans = [0] * (n+m-1)
            for i in range(n):
                for j in range(m):
                    ans[i+j] += a[i] * b[j]
                    ans[i+j] %= mod
            return ans
        z = 1 << self._ceil_pow2(n+m-1)
        a += [0] * (z-n)
        self._butterfly(a,mod)
        b += [0] * (z-m)
        self._butterfly(b,mod)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= mod
        self._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

ans = Convolution().convolution_mod(A,B,MOD)
print(*ans)

Solution (Python):
p, g = 998244353, 3
def convolve(a, b):
    def fft(f):
        for l in range(k)[::-1]:
            d = 1 << l
            v = W[k-1-l]
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p

    def ifft(f):
        for l in range(k):
            d = 1 << l
            v = iW[k-1-l]
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
 
    n0, n1 = len(a), len(b)
    k = (max(n0, n1) - 1).bit_length() + 1
    n = 1 << k
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    W = [w]
    for i in range(k):
        W.append(W[-1] ** 2 % p)
    invw = pow(w, p-2, p)
    iW = [invw]
    for i in range(k):
        iW.append(iW[-1] ** 2 % p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):
p, g = 998244353, 3
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):
def fft(f, n, w, p, g):
    d = n // 2
    v = w
    while d >= 1:
        u = 1
        for i in range(d):
            for j in range(i, n, 2*d):
                f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
            u = u * v % p
        v = v * v % p
        d //= 2
def ifft(f, n, invw, p, g):
    d = 1
    while d < n:
        v = pow(invw, n // (2 * d), p)
        u = 1
        for i in range(d):
            for j in range(i, n, 2*d):
                f[j+d] *= u
                f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
            u = u * v % p
        d *= 2
def convolve(a, b):
    p, g = 998244353, 3
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a, n, w, p, g), fft(b, n, w, p, g)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a, n, invw, p, g)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))

Solution (Python):

code = """






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

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)

cpdef 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 inline void printLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

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


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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):

code = """






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))

Solution (Python):
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))