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):
class Convolution:

    ROOT = 3

    def __init__(self, mod):
        self.MOD = mod

    def __butterfly(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        MOD = self.MOD
        sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601,
                 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
        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(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        MOD = self.MOD
        sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543,
                  109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)
        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 __call__(self, a, b):
        n = len(a)
        m = len(b)
        MOD = self.MOD
        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 atcoder_practice2_f():
    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()]

    convolution = Convolution(998244353)
    print(*convolution(A, B))


if __name__ == "__main__":
    atcoder_practice2_f()

Solution (Python):
class Convolution:
    sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
    sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)
    ROOT = 3
    def __init__(self, mod):
        self.MOD = mod

    def __butterfly(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        MOD = self.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 *= Convolution.sum_e[(~s & -~s).bit_length() - 1]
                now %= MOD

    def __butterfly_inv(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        MOD = self.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 *= Convolution.sum_ie[(~s & -~s).bit_length() - 1]
                inow %= MOD

    def __call__(self, a, b):
        n = len(a)
        m = len(b)
        MOD = self.MOD
        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 atcoder_practice2_f():
    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()]

    convolution = Convolution(998244353)
    print(*convolution(A, B))


if __name__ == "__main__":
    atcoder_practice2_f()

Solution (Python):
class Convolution:
    sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
    sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)
    ROOT = 3
    def __init__(self, mod):
        self.MOD = mod

    def __butterfly(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        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) % self.MOD
                    arr[i + offset + p] = (l - r) % self.MOD
                now *= Convolution.sum_e[(~s & -~s).bit_length() - 1]
                now %= self.MOD

    def __butterfly_inv(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        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) % self.MOD
                    arr[i + offset + p] = (self.MOD + l - r) * inow % self.MOD
                inow *= Convolution.sum_ie[(~s & -~s).bit_length() - 1]
                inow %= self.MOD

    def __call__(self, a, b):
        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] %= self.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] %= self.MOD
        self.__butterfly_inv(a)
        a = a[:n + m - 1]
        iz = pow(z, self.MOD - 2, self.MOD)
        for i in range(n + m - 1):
            a[i] *= iz
            a[i] %= self.MOD
        return a




def atcoder_practice2_f():
    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()]

    convolution = Convolution(998244353)
    print(*convolution(A, B))


if __name__ == "__main__":
    atcoder_practice2_f()

Solution (Python):

import numpy as np
mod = 998244353


def convolve(A, B):
    n = len(A) + len(B) - 1
    fftlen = 1 << (n-1).bit_length()
    fa = np.fft.rfft(A, fftlen)
    fb = np.fft.rfft(B, fftlen)
    inv = (np.fft.irfft(fa * fb, fftlen) + 0.5).astype(np.int64)
    return inv[:n]


def mod_convolve_15(A, B, mod):
    a1, a2 = np.divmod(A, 1 << 15)
    b1, b2 = np.divmod(B, 1 << 15)
    x = convolve(a1, b1) % mod
    y = convolve(a2, b2) % mod
    xy = (convolve(a1 + a2, b1 + b2) - (x + y)) % mod
    res = (x << 30) + (xy << 15) + y
    return res % mod


def mod_convolve_10(A, B, mod):
    a1, a2 = np.divmod(A, 1 << 20)
    a2, a3 = np.divmod(a2, 1 << 10)
    b1, b2 = np.divmod(B, 1 << 20)
    b2, b3 = np.divmod(b2, 1 << 10)
    x = convolve(a1, b1) % mod
    y = convolve(a2, b2) % mod
    z = convolve(a3, b3) % mod
    xy = (convolve(a1 + a2, b1 + b2) - (x + y)) % mod
    yz = (convolve(a2 + a3, b2 + b3) - (y + z)) % mod
    zx = (convolve(a3 + a1, b3 + b1) - (z + x)) % mod
    res = ((((x << 20) % mod) << 20) +
           (((xy << 20) % mod) << 10) +
           ((y + zx) << 20) +
           (yz << 10) % mod + z) % mod
    return res


N, M = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
B = np.array(input().split(), dtype=np.int64)
C = mod_convolve_10(A, B, mod)
print(*C, sep=" ")

Solution (Python):
MOD = 998244353
PROOT = 3
IPROOT = 665496235
roots  = [pow(PROOT,(MOD-1)>>i,MOD) for i in range(24)] 
iroots  = [pow(IPROOT,(MOD-1)>>i,MOD) for i in range(24)] 

def fft_stockham(A,n,inv=False):
    N = 1<<n
    for i in range(n):
        nA = [0]*N
        a = 1<<i
        b = 1<<(n-i-1)
        wb = iroots[i+1] if inv else roots[i+1]
        for j in range(b):
            w = 1
            for k in range(a):
                nA[2*a*j+k]   = (A[a*j+k] + A[a*j+N//2+k]*w)%MOD
                nA[2*a*j+k+a] = (A[a*j+k] - A[a*j+N//2+k]*w)%MOD
                w = w*wb%MOD
        A = nA
    return A
  
def convolution(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))
    fa = fft_stockham(a,n)
    fb = fft_stockham(b,n)

    inv = pow(1<<n,MOD-2,MOD)
    for i in range(N):
      fa[i] = fa[i]*fb[i]%MOD*inv%MOD
    ab = fft_stockham(fa,n,True)
    return ab[:deg+1]

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = convolution(a,b)
print(*c)

Solution (Python):


MOD = 998244353
ROOT = 3

sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)

def butterfly(arr):
    n = len(arr)
    h = (n - 1).bit_length()
    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):
    n = len(arr)
    h = (n - 1).bit_length()
    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):
    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)
    butterfly(a)
    butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    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 autocorrelation(a):
    n = len(a)
    if not n: return []
    if n <= 50:
        res = [0] * (2 * n - 1)
        for i in range(n):
            for j in range(n):
                res[i + j] += a[i] * a[j]
                res[i + j] %= MOD
        return res
    z = 1 << (2 * n - 2).bit_length()
    a += [0] * (z - n)
    butterfly(a)
    for i in range(a):
        a[i] *= a[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:2 * n - 1]
    iz = pow(z, MOD - 2, MOD)
    for i in range(2 * n - 1):
        a[i] *= iz
        a[i] %= MOD
    return a

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

print(*convolution(A, B))

Solution (Python):


MOD = 998244353
ROOT = 3

sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)

def butterfly(arr):
    n = len(arr)
    h = (n - 1).bit_length()
    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):
    n = len(arr)
    h = (n - 1).bit_length()
    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):
    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)
    butterfly(a)
    butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    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 autocorrelation(a):
    n = len(a)
    if not n: return []
    if n <= 50:
        res = [0] * (2 * n - 1)
        for i in range(n):
            for j in range(n):
                res[i + j] += a[i] * a[j]
                res[i + j] %= MOD
        return res
    z = 1 << (2 * n - 2).bit_length()
    a += [0] * (z - n)
    butterfly(a)
    for i in range(a):
        a[i] *= a[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:2 * n - 1]
    iz = pow(z, MOD - 2, MOD)
    for i in range(2 * n - 1):
        a[i] *= iz
        a[i] %= MOD
    return a

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

print(*convolution(A, B))

Solution (Python):
MOD = 998244353
ROOT = 3

class Convolution_998244353(): 
    def __init__(self):
        self.sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
        self.sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)

    def butterfly(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        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):
        n = len(arr)
        h = (n - 1).bit_length()
        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):
        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 autocorrelation(self, a):
        n = len(a)
        if not n: return []
        if n <= 50:
            res = [0] * (2 * n - 1)
            for i in range(n):
                for j in range(n):
                    res[i + j] += a[i] * a[j]
                    res[i + j] %= MOD
            return res
        z = 1 << (2 * n - 2).bit_length()
        a += [0] * (z - n)
        self.butterfly(a)
        for i in range(a):
            a[i] *= a[i]
            a[i] %= MOD
        self.butterfly_inv(a)
        a = a[:2 * n - 1]
        iz = pow(z, MOD - 2, MOD)
        for i in range(2 * n - 1):
            a[i] *= iz
            a[i] %= MOD
        return a

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):
MOD = 998244353
ROOT = 3

class Convolution_998244353():
    def __init__(self):
        self.sum_e = [911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        self.sum_ie = [86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0]


    def butterfly(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        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):
        n = len(arr)
        h = (n - 1).bit_length()
        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):
        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 autocorrelation(self, a):
        n = len(a)
        if not n: return []
        if n <= 50:
            res = [0] * (2 * n - 1)
            for i in range(n):
                for j in range(n):
                    res[i + j] += a[i] * a[j]
                    res[i + j] %= MOD
            return res
        z = 1 << (2 * n - 2).bit_length()
        a += [0] * (z - n)
        self.butterfly(a)
        for i in range(a):
            a[i] *= a[i]
            a[i] %= MOD
        self.butterfly_inv(a)
        a = a[:2 * n - 1]
        iz = pow(z, MOD - 2, MOD)
        for i in range(2 * n - 1):
            a[i] *= iz
            a[i] %= MOD
        return a

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):
MOD = 998244353
ROOT = 3

class Convolution_998244353():
    def __init__(self):
        self.first1 = True
        self.first2 = True
        self.sum_e = [0] * 30
        self.sum_ie = [0] * 30

    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):
        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(ROOT, 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):
        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(ROOT, 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):
        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 autocorrelation(self, a):
        n = len(a)
        if not n: return []
        if n <= 50:
            res = [0] * (2 * n - 1)
            for i in range(n):
                for j in range(n):
                    res[i + j] += a[i] * a[j]
                    res[i + j] %= MOD
            return res
        z = 1 << (2 * n - 2).bit_length()
        a += [0] * (z - n)
        self.butterfly(a)
        for i in range(a):
            a[i] *= a[i]
            a[i] %= MOD
        self.butterfly_inv(a)
        a = a[:2 * n - 1]
        iz = pow(z, MOD - 2, MOD)
        for i in range(2 * n - 1):
            a[i] *= iz
            a[i] %= MOD
        return a

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):
import sys
import numpy as np
input = sys.stdin.readline

def convolute(a, b, n, m, M):
    l = 1
    while 2 * l < len(a) + len(b) - 1:
        l *= 2
    l *= 2
    A = np.fft.rfft(a, l)
    B = np.fft.rfft(b, l)
    C = A * B
    c = np.fft.irfft(C, l)
    c = np.rint(c).astype(np.int64)
    return c

def convolute_large(a, b, n, m, M):
    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 = convolute(a1, b1, n, m, M) % M
    bb = convolute(a2, b2, n, m, M) % M
    cc = convolute(a3, b3, n, m, M) % M
    dd = (convolute(a1+a2, b1+b2, n, m, M) - (aa+bb)) % M
    ee = (convolute(a2+a3, b2+b3, n, m, M) - (bb+cc)) % M
    ff = (convolute(a1+a3, b1+b3, n, m, M) - (aa+cc)) % M
    h = (((aa*d*d)%M)*d*d + ((dd*d*d)%M)*d + (bb+ff)*d*d + ee*d + cc) % M
    return h

def main():
    n, m = list(map(int, input().split()))  
    a = np.array(input().split(), dtype=np.int64)
    b = np.array(input().split(), dtype=np.int64)

    M = 998244353
    c = convolute_large(a, b, n, m, M)[:n+m-1]
    print(*c)

if __name__ == "__main__":
    main()