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):
code = r"""




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

Solution (Python):
import numpy as np
from numpy.fft import rfft,irfft



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

Solution (Python):
code = r"""


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

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

Solution (Python):
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 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):
    n = len(a)
    m = len(b)
    if not n or not m: return []
    if min(n, m) <= 0:
        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]
        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

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

Solution (Python):
class Convolution:
  def __init__(s, MOD):
    s.MOD = MOD
    s.PrimitiveRoot = s.primitive_root(MOD)
    s._BIT_TABLE = [0] * 64
    _BIT_HASH = 0x03F566ED27179461
    for i in range(64):
      s._BIT_TABLE[_BIT_HASH >> 58] = i
      _BIT_HASH <<= 1
      _BIT_HASH &= 0xFFFFFFFFFFFFFFFF

  def convolution(s, a, b):
    n, m = len(a), 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
      ans = [0] * (n + m - 1)
      for i in range(n):
        for j in range(m):
          ans[i + j] = (ans[i + j] + a[i] * b[j]) % s.MOD
      return ans
    z = 1 << s.ceil_pow2(n + m - 1)
    a = a + [0] * (z - n)
    a = s.butterfly(a)
    b = b + [0] * (z - m)
    b = s.butterfly(b)
    for i in range(z): a[i] = a[i] * b[i] % s.MOD
    a = s.butterfly_inv(a)
    iz = pow(z, s.MOD - 2, s.MOD)
    for i in range(n + m - 1): a[i] = a[i] * iz % s.MOD
    return a[:n + m - 1]

  def butterfly(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_e = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_e[i] = es[i] * now % s.MOD
        now = now * ies[i] % s.MOD
    for ph in range(1, h + 1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      now = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p] * now % s.MOD
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (l - r) % s.MOD
        now = now * sum_e[s.bsf(~ss)] % s.MOD
    return a

  def butterfly_inv(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_ie = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_ie[i] = ies[i] * now % s.MOD
        now = now * es[i] % s.MOD
    for ph in range(h, 0, -1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      inow = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p]
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (s.MOD + l - r) * inow % s.MOD
        inow = inow * sum_ie[s.bsf(~ss)] % s.MOD
    return a

  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

  def bsf(s, n):
    if n == 0: return 64
    x = n
    y = x & -x
    i = ((y * 0x03F566ED27179461) & 0xFFFFFFFFFFFFFFFF) >> 58
    return s._BIT_TABLE[i]

  def prime(s, x):
    L, U = [], []
    i = 1
    while i * i <= x:
      if x % i == 0:
        L.append(i)
        if i != x // i:
          U.append(x // i)
      i += 1
    return L + U[::-1]

  def primitive_root(s, x):
    L = s.prime(x - 1)
    a, i = 2, 0
    k = len(L) - 1
    while i != k:
      if pow(a, L[i], x) == 1:
        a += 1
        i = 0
      else:
        i += 1
    return a


N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 998244353
conv = Convolution(MOD)
ans = conv.convolution(a, b)
print(" ".join(list(map(str, ans))))

Solution (Python):
class Convolution:
  def __init__(s, MOD):
    s.MOD = MOD
    s.PrimitiveRoot = s.primitive_root(MOD)
    s._BIT_TABLE = [0] * 64
    _BIT_HASH = 0x03F566ED27179461
    for i in range(64):
      s._BIT_TABLE[_BIT_HASH >> 58] = i
      _BIT_HASH <<= 1
      _BIT_HASH &= 0xFFFFFFFFFFFFFFFF

  def convolution(s, a, b):
    n, m = len(a), len(b)
    if not n or not m: return []
    c = s.convolutionModInt(a, b)
    return c

  def convolutionModInt(s, a, b):
    n, m = len(a), 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
      ans = [0] * (n + m - 1)
      for i in range(n):
        for j in range(m):
          ans[i + j] = (ans[i + j] + a[i] * b[j]) % s.MOD
      return ans
    z = 1 << s.ceil_pow2(n + m - 1)
    a = a + [0] * (z - n)
    a = s.butterfly(a)
    b = b + [0] * (z - m)
    b = s.butterfly(b)
    for i in range(z): a[i] = a[i] * b[i] % s.MOD
    a = s.butterfly_inv(a)
    iz = pow(z, s.MOD - 2, s.MOD)
    for i in range(n + m - 1): a[i] = a[i] * iz % s.MOD
    return a[:n + m - 1]

  def butterfly(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_e = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_e[i] = es[i] * now % s.MOD
        now = now * ies[i] % s.MOD
    for ph in range(1, h + 1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      now = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p] * now % s.MOD
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (l - r) % s.MOD
        now = now * sum_e[s.bsf(~ss)] % s.MOD
    return a

  def butterfly_inv(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_ie = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_ie[i] = ies[i] * now % s.MOD
        now = now * es[i] % s.MOD
    for ph in range(h, 0, -1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      inow = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p]
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (s.MOD + l - r) * inow % s.MOD
        inow = inow * sum_ie[s.bsf(~ss)] % s.MOD
    return a

  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

  def bsf(s, n):
    if n == 0: return 64
    x = n
    y = x & -x
    i = ((y * 0x03F566ED27179461) & 0xFFFFFFFFFFFFFFFF) >> 58
    return s._BIT_TABLE[i]

  def prime(s, x):
    L, U = [], []
    i = 1
    while i * i <= x:
      if x % i == 0:
        L.append(i)
        if i != x // i:
          U.append(x // i)
      i += 1
    return L + U[::-1]

  def primitive_root(s, x):
    L = s.prime(x - 1)[:-1]
    a = 2
    i = 0
    k = len(L)
    while i != k:
      if pow(a, L[i], x) == 1:

        a += 1
        i = 0
      else:
        i += 1
    return a


N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 998244353
conv = Convolution(MOD)
ans = conv.convolution(a, b)
print(" ".join(list(map(str, ans))))

Solution (Python):
class Convolution:
  def __init__(s, MOD):
    s.MOD = MOD
    s.PrimitiveRoot = s.primitive_root(MOD)
    s._BIT_TABLE = [0] * 64
    _BIT_HASH = 0x03F566ED27179461
    for i in range(64):
      s._BIT_TABLE[_BIT_HASH >> 58] = i
      _BIT_HASH <<= 1
      _BIT_HASH &= 0xFFFFFFFFFFFFFFFF

  def convolution(s, a, b):
    n, m = len(a), len(b)
    if not n or not m: return []
    c = s.convolutionModInt(a, b)
    return c

  def convolutionModInt(s, a, b):
    n, m = len(a), 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
      ans = [0] * (n + m - 1)
      for i in range(n):
        for j in range(m):
          ans[i + j] = (ans[i + j] + a[i] * b[j]) % s.MOD
      return ans
    z = 1 << s.ceil_pow2(n + m - 1)
    a = a + [0] * (z - n)
    a = s.butterfly(a)
    b = b + [0] * (z - m)
    b = s.butterfly(b)
    for i in range(z): a[i] = a[i] * b[i] % s.MOD
    a = s.butterfly_inv(a)
    iz = pow(z, s.MOD - 2, s.MOD)
    for i in range(n + m - 1): a[i] = a[i] * iz % s.MOD
    return a[:n + m - 1]

  def butterfly(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_e = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_e[i] = es[i] * now % s.MOD
        now = now * ies[i] % s.MOD
    for ph in range(1, h + 1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      now = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p] * now % s.MOD
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (l - r) % s.MOD
        now = now * sum_e[s.bsf(~ss)] % s.MOD
    return a

  def butterfly_inv(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_ie = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_ie[i] = ies[i] * now % s.MOD
        now = now * es[i] % s.MOD
    for ph in range(h, 0, -1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      inow = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p]
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (s.MOD + l - r) * inow % s.MOD
        inow = inow * sum_ie[s.bsf(~ss)] % s.MOD
    return a

  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

  def bsf(s, n):
    if n == 0: return 64
    x = n
    y = x & -x
    i = ((y * 0x03F566ED27179461) & 0xFFFFFFFFFFFFFFFF) >> 58
    return s._BIT_TABLE[i]

  def prime(s, x):
    L = []
    for i in range(1, int(x ** (1 / 2)) + 1):
      if x % i == 0:
        L.append(i)
        if i != x // i:
          L.append(x // i)
    L.sort()
    return L

  def primitive_root(s, x):
    L = s.prime(x - 1)[:-1]
    a = 2
    i = 0
    k = len(L)
    while i != k:
      if pow(a, L[i], x) == 1:

        a += 1
        i = 0
      else:
        i += 1
    return a


N, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 998244353
conv = Convolution(MOD)
ans = conv.convolution(a, b)
print(" ".join(list(map(str, ans))))

Solution (Python):
mod = 998244353
primitive_root = 3
roots = [pow(primitive_root, (mod-1)>>i, mod) for i in range(24)]
inv_roots = [pow(root, mod-2, mod) for root in roots]

def ntt(A, n):
    for i in range(n):
        m = 1<<(n-i-1)
        for s in range(1<<i):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m])%mod, (A[s+j]-A[s+j+m])*w%mod
                w *= roots[n-i]
                w %= mod

def intt(A, n):
    for i in range(n):
        m = 1<<i
        for s in range(1<<(n-i-1)):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m]*w)%mod, (A[s+j]-A[s+j+m]*w)%mod
                w *= inv_roots[i+1]
                w %= mod
    inv = pow((mod+1)//2, n, mod)
    for i in range(1<<n):
        A[i] *= inv
        A[i] %= mod

def convolution(A, B):
    la = len(A)
    lb = len(B)
    deg = la + lb - 2
    n = deg.bit_length()
    N = 1<<n
    A += [0]*(N-la)
    B += [0]*(N-lb)
    ntt(A, n)
    ntt(B, n)
    A = [a*b%mod for a, b in zip(A, B)]
    intt(A, n)
    return A[:deg+1]


import sys
input = sys.stdin.readline
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):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  




mod = 998244353
primitive_root = 3  
roots = [pow(primitive_root,(mod-1) >> i,mod) for i in range(24)]
inv_roots = [pow(r,mod-2,mod) for r in roots]





def ntt(A,n):
    for i in range(n):
        m = 1 << (n-i-1)
        for start in range(1 << i):
            w = 1
            start *= m*2
            for j in range(m):
                A[start+j],A[start+j+m] = (A[start+j]+A[start+j+m]) % mod,(A[start+j]-A[start+j+m])*w % mod
                w *= roots[n-i]
                w %= mod
    return A


def inv_ntt(A,n):
    for i in range(n):
        m = 1 << i
        for start in range(1 << (n-i-1)):
            w = 1
            start *= m*2
            for j in range(m):
                A[start+j],A[start+j+m] = (A[start+j]+A[start+j+m]*w) % mod,(A[start+j]-A[start+j+m]*w) % mod
                w *= inv_roots[i+1]
                w %= mod
    a = pow(2,n*(mod-2),mod)
    for i in range(1 << n):
        A[i] *= a
        A[i] %= mod
    return A


def convolution(A,B):
    a,b = len(A),len(B)
    deg = a+b-2
    n = deg.bit_length()
    N = 1 << n
    A += [0]*(N-a)  
    B += [0]*(N-b)  
    A = ntt(A,n)
    B = ntt(B,n)
    C = [(A[i]*B[i]) % mod for i in range(N)]
    C = inv_ntt(C,n)
    return C[:deg+1]


N,M = MI()
A,B = LI(),LI()
print(*convolution(A,B))