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):
from numba import jit, njit, i8
import numpy as np


@njit(i8(i8, i8, i8), cache=True)
def modpow(a, p, m):
  r = 1
  while p:
    if p & 1: r = r * a % m
    a = a * a % m
    p >>= 1
  return r


@njit(i8[:](i8[:], i8[:]), cache=True)
def ntt(s, t):
  mod = 998244353
  pr = 5
  sl, tl = len(s), len(t)
  k = 1
  M = 2
  while M < sl + tl - 1:
    k += 1
    M *= 2
  w = np.zeros(M // 2, np.int64)
  y = np.zeros(M // 2, np.int64)

  def init():
    nonlocal w, y, M, mod, pr
    z = modpow(pr, (mod - 1) // M, mod)
    x = modpow(z, mod - 2, mod)
    j = M // 4
    while j:
      w[j] = z
      z = z * z % mod
      y[j] = x
      x = x * x % mod
      j //= 2
    y[0] = 1
    w[0] = 1
    j = M // 2
    js = 2
    while js < j:
      z = w[js]
      x = y[js]
      for k2 in range(js):
        w[k2 + js] = w[k2] * z % mod
        y[k2 + js] = y[k2] * x % mod
      js *= 2

  def fft(a, k):
    nonlocal w, y, mod
    m = 2 ** k
    u = 1
    v = m // 2
    i = k
    while i:
      jh = 0
      while jh < u:
        wj = w[jh]
        j = jh * v * 2
        je = j + v
        while j < je:
          ajv = wj * a[j + v] % mod
          a[j + v] = a[j] + mod - ajv
          if a[j + v] >= mod:
            a[j + v] -= mod
          a[j] = a[j] + ajv
          if a[j] >= mod:
            a[j] -= mod
          j += 1
        jh += 1
      u *= 2
      v //= 2
      i -= 1

  def ifft(a, k):
    nonlocal w, y, mod
    m = 2 ** k
    u = m // 2
    v = 1
    i = 1
    while i <= k:
      jh = 0
      while jh < u:
        wj = y[jh]
        j = jh * v * 2
        je = j + v
        while j < je:
          ajv = a[j] + mod - a[j + v]
          if ajv >= mod:
            ajv -= mod
          a[j] = a[j] + a[j + v]
          if a[j] >= mod:
            a[j] -= mod
          a[j + v] = wj * ajv % mod
          j += 1
        jh += 1
      u //= 2
      v *= 2
      i += 1

  init()
  u = np.zeros(M, np.int64); u[:sl] = s; fft(u, k)
  v = np.zeros(M, np.int64); v[:tl] = t; fft(v, k)
  u *= v; u %= mod; ifft(u, k)
  u *= modpow(2 ** k, mod - 2, mod); u %= mod
  return u[:sl + tl - 1]



import sys
readline = sys.stdin.buffer.readline
N, M = map(int, readline().split())
A = np.array(readline().split(), np.int64)
B = np.array(readline().split(), np.int64)
print(' '.join(map(str, ntt(A, B))))

Solution (Python):


omega = 565042129
n = 2 ** 20
mod = 998244353
rev = pow(omega, mod - 2, mod)



def bit_reverse(d):
	n = len(d)
	ns = n >> 1; nss = ns >> 1
	ns1 = ns + 1
	i = 0
	for j in range(0, ns, 2):
		if j < i:
			d[i], d[j] = d[j], d[i]
			d[i + ns1], d[j + ns1] = d[j + ns1], d[i + ns1]
		d[i + 1], d[j + ns] = d[j + ns], d[i + 1]
		k = nss; i ^= k
		while k > i:
			k >>= 1; i ^= k
	return d


def fmt_bu(A, n, base, half, Q):
	N = n
	m = 1
	while n > 1:
		n >>= 1
		
		w = pow(base, n, Q)
		wk = 1
		for j in range(m):
			for i in range(j, N, 2 * m):
				
				U = A[i]; V = (A[i + m] * wk) % Q
				A[i] = (U + V) % Q
				
				A[i + m] = (U + V * half) % Q
			wk = (wk * w) % Q
		m <<= 1
	return A


def fmt(f, l, Q = mod):
	if l == 1: return f
	A = f[:]
	
	bit_reverse(A)
	return fmt_bu(A, n, omega, pow(omega, n // 2, Q), Q)


def ifmt(F, l, Q = mod):
	if l == 1: return F
	A = F[:]
	
	bit_reverse(A)
	
	f = fmt_bu(A, n, rev, pow(rev, n // 2, Q), Q)
	
	n_rev = pow(n, Q - 2, Q)
	return [(e * n_rev) % Q for e in f]


def convolute(a, b, l, Q = mod):
	A = fmt(a, l, Q)
	B = fmt(b, l, Q)
	C = [(s * t) % Q for s, t in zip(A, B)]
	c = ifmt(C, l, Q)
	return c

def getlist():
	return list(map(int, input().split()))

N, M = getlist()
A = getlist()
B = getlist()


A += [0] * (n - N)
B += [0] * (n - M)
fg = convolute(A, B, n)
print(*fg[:N + M - 1])

Solution (Python):
def NTT(A,Mod,primitive=None,inverse=False):
    n=len(A)
    max_level=(n-1).bit_length()
    m=1<<max_level

    u=Mod-1
    e=0
    while u%2==0:
        e+=1
        u>>=1

    w=pow(primitive,u,Mod)

    if inverse: 
        w=pow(w,Mod-2,Mod) 

    W=[0]*(e+1)
    W[-1]=w

    for k in range(e-1,-1,-1):
        W[k]=(W[k+1]*W[k+1])%Mod

    U=[[0]*(1<<x) for x in range(max_level+1)]

    for y in range(1,max_level+1):
        for x in range(1<<y):
            if x==0:
                U[y][x]=1
            else:
                U[y][x]=(U[y][x-1]*W[y])%Mod

    def ntt(x,level):
        t=len(x)
        if t==1:
            return x

        y=[0]*(t>>1)
        z=[0]*(t>>1)

        for k in range(t//2):
            y[k]=(x[k]+x[k+t//2])%Mod
            z[k]=((x[k]-x[k+t//2])*U[level][k])%Mod

        y=ntt(y,level-1)
        z=ntt(z,level-1)

        x=[0]*t
        for k in range(t>>1):
            x[2*k]=y[k]
            x[2*k+1]=z[k]

        return x

    B=A+[0]*(m-n)
    return ntt(B,max_level)

def Inverse_NTT(A,Mod,primitive=None):
    B=NTT(A,Mod,primitive,inverse=True)
    N_inv=pow(len(A),Mod-2,Mod)
    return [(N_inv*b)%Mod for b in B]

def Convolution_Mod(A,B,Mod,primitive=None):
    N=len(A);M=len(B)
    if N==0 or M==0:
        return []

    z=1<<((N+M-2).bit_length())

    A=A+[0]*(z-N)
    B=B+[0]*(z-M)

    P=NTT(A,Mod,primitive)
    Q=NTT(B,Mod,primitive)

    R=[(P[i]*Q[i])%Mod for i in range(z)]

    return Inverse_NTT(R,Mod,primitive)

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

C=Convolution_Mod(A,B,Mod,3)
print(" ".join(map(lambda x:str(x%Mod),C[:N+M-1])))

Solution (Python):
ROOT = 3
MOD = 998244353
roots  = [pow(ROOT,(MOD-1)>>i,MOD) for i in range(24)] 
iroots = [pow(x,MOD-2,MOD) for x in roots] 

def untt(a,n):
    for i in range(n):
        m = 1<<(n-i-1)
        for s in range(1<<i):
            w_N = 1
            s *= m*2
            for p in range(m):
                a[s+p], a[s+p+m] = (a[s+p]+a[s+p+m])%MOD, (a[s+p]-a[s+p+m])*w_N%MOD
                w_N = w_N*roots[n-i]%MOD

def iuntt(a,n):
    for i in range(n):
        m = 1<<i
        for s in range(1<<(n-i-1)):
            w_N = 1
            s *= m*2
            for p in range(m):
                a[s+p], a[s+p+m] = (a[s+p]+a[s+p+m]*w_N)%MOD, (a[s+p]-a[s+p+m]*w_N)%MOD
                w_N = w_N*iroots[i+1]%MOD
            
    inv = pow((MOD+1)//2,n,MOD)
    for i in range(1<<n):
        a[i] = a[i]*inv%MOD

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))
    untt(a,n)
    untt(b,n)
    for i in range(N):
      a[i] = a[i]*b[i]%MOD
    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()))
c = convolution(a,b)
print(*c)

Solution (Python):



class convolution:
    def __init__(self, mod: int):
        self.MOD = mod
        self.g = self.__primitive_root_constexpr()
    
    def convolution(self, a: list, b: list) -> list:
        n, m = len(a), len(b)
        mod = self.MOD
        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] += a[i] * b[j] % mod
                    ans[i + j] %= mod
            return ans
        z = 1 << self.ceil_pow2(n + m - 1)
        a = self.resize(a, z)
        a = self.butterfly(a)
        b = self.resize(b, z)
        b = self.butterfly(b)
        a = [a[i] * b[i] % mod for i in range(z)]
        a = self.butterfly_inv(a)
        a = a[:n + m - 1]
        iz = self.inv(z)
        a = [x * iz % self.MOD for x in a]
        return a

    def butterfly(self, a: list) -> list:
        n = len(a)
        h = self.ceil_pow2(n)
        first = True
        sum_e = [0] * 30
        m = self.MOD
        if first:
            first = False
            es, ies = [0] * 30, [0] * 30
            cnt2 = self.bsf(m - 1)
            e = self.mypow(self.g, (m - 1) >> cnt2); ie = self.inv(e)
            for i in range(cnt2, 1, -1):
                es[i - 2] = e
                ies[i - 2] = ie
                e = e * e % m
                ie = ie * ie % m
            now = 1
            for i in range(cnt2 - 2):
                sum_e[i] = es[i] * now % m
                now = now * ies[i] % m
        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] % m
                    r = a[i + offset + p] * now % m
                    a[i + offset] = (l + r) % m
                    a[i + offset + p] = (l - r) % m
                now = now * sum_e[self.bsf(~s)] % m
        return a

    def butterfly_inv(self, a: list) -> list:
        n = len(a)
        h = self.ceil_pow2(n)        
        first = True
        sum_ie = [0] * 30
        m = self.MOD
        if first:
            first = False
            es, ies = [0] * 30, [0] * 30
            cnt2 = self.bsf(m - 1)
            e = self.mypow(self.g, (m - 1) >> cnt2); ie = self.inv(e)
            for i in range(cnt2, 1, -1):
                es[i - 2] = e
                ies[i - 2] = ie
                e = e * e % m
                ie = ie * ie % m
            now = 1
            for i in range(cnt2 - 2):
                sum_ie[i] = ies[i] * now % m
                now = es[i] * now % m
        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] % m
                    r = a[i + offset + p] % m
                    a[i + offset] = (l + r) % m
                    a[i + offset + p] = (m + l - r) * inow % m
                inow = sum_ie[self.bsf(~s)] * inow % m
        return a

    @staticmethod
    def resize(array: list, sz: int) -> list:
        new_array = array + [0] * (sz - len(array))
        return new_array
    @staticmethod
    def ceil_pow2(n: int) -> int:
        x = 0
        while (1 << x) < n: x += 1
        return x
    @staticmethod
    def bsf(n: int) -> int:
        return (n & -n).bit_length() - 1
    def inv(self, x: int):
        if self.__is_prime_constexpr():
            assert x
            return self.mypow(x, self.MOD - 2)
        else:
            eg = self.__inv_gcd(x)
            assert eg[0] == 1
            return eg[1]
    def mypow(self, x: int, n: int) -> int:
        assert 0 <= n
        r = 1
        while n:
            if n & 1: r = r * x % self.MOD
            x = x * x % self.MOD
            n >>= 1
        return r
    
    def __is_prime_constexpr(self) -> bool:
        n = self.MOD
        if n <= 1: return False
        if n == 2 or n == 7 or n == 61: return True
        if n % 2 == 0: return False
        d = n - 1
        while d % 2 == 0: d //= 2
        for a in [2, 7, 61]:
            t = d
            y = self.__pow_mod_constexpr(a, t, n)
            while t != n - 1 and y != 1 and y != n - 1:
                y = y * y % n
                t <<= 1
            if y != n - 1 and t % 2 == 0: return False
        return True
    def __pow_mod_constexpr(self, x: int, n: int, m: int) -> int:
        if m == 1: return 0
        _m = m; r = 1; y = self.__safe_mod(x, m)
        while n:
            if n & 1: r = (r * y) % _m
            y = (y * y) % _m
            n >>= 1
        return r
    def __safe_mod(self, x: int, m: int) -> int:
        x %= m
        if x < 0: x += m
        return x
    def __inv_gcd(self, a: int) -> tuple:
        b = self.MOD; a = safe_mod(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
            tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp
        if m0 < 0: m0 += b // s
        return (s, m0)
    def __primitive_root_constexpr(self) -> int:
        m = self.MOD
        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
        divs[0] = 2
        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 self.__pow_mod_constexpr(g, (m - 1) // divs[i], m) == 1:
                    ok = False
                    break
            if ok: return g
            g += 1







import sys









MOD = 998244353
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, m = read_ints()
    a = read_int_list()
    b = read_int_list()
    a = [x % MOD for x in a]
    b = [x % MOD for x in b]
    cnv = convolution(MOD)
    ans = cnv.convolution(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()

Solution (Python):



class convolution:
    def __init__(self, mod: int):
        self.MOD = mod
        self.g = self.__primitive_root_constexpr()
    
    def convolution(self, a: list, b: list) -> list:
        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] += a[i] * b[j] % self.MOD
                    ans[i + j] %= self.MOD
            return ans
        z = 1 << self.ceil_pow2(n + m - 1)
        a = self.resize(a, z)
        a = self.butterfly(a)
        b = self.resize(b, z)
        b = self.butterfly(b)
        for i in range(z): a[i] = a[i] * b[i] % self.MOD
        a = self.butterfly_inv(a)
        a = a[:n + m - 1]
        iz = self.inv(z)
        a = [x * iz % self.MOD for x in a]
        return a

    def butterfly(self, a: list) -> list:
        n = len(a)
        h = self.ceil_pow2(n)
        first = True
        sum_e = [0] * 30
        m = self.MOD
        if first:
            first = False
            es, ies = [0] * 30, [0] * 30
            cnt2 = self.bsf(m - 1)
            e = self.mypow(self.g, (m - 1) >> cnt2); ie = self.inv(e)
            for i in range(cnt2, 1, -1):
                es[i - 2] = e
                ies[i - 2] = ie
                e = e * e % m
                ie = ie * ie % m
            now = 1
            for i in range(cnt2 - 2):
                sum_e[i] = es[i] * now % m
                now = now * ies[i] % m
        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] % m
                    r = a[i + offset + p] * now % m
                    a[i + offset] = (l + r) % m
                    a[i + offset + p] = (l - r) % m
                now = now * sum_e[self.bsf(~s)] % m
        return a

    def butterfly_inv(self, a: list) -> list:
        n = len(a)
        h = self.ceil_pow2(n)        
        first = True
        sum_ie = [0] * 30
        m = self.MOD
        if first:
            first = False
            es, ies = [0] * 30, [0] * 30
            cnt2 = self.bsf(m - 1)
            e = self.mypow(self.g, (m - 1) >> cnt2); ie = self.inv(e)
            for i in range(cnt2, 1, -1):
                es[i - 2] = e
                ies[i - 2] = ie
                e = e * e % m
                ie = ie * ie % m
            now = 1
            for i in range(cnt2 - 2):
                sum_ie[i] = ies[i] * now % m
                now = es[i] * now % m
        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] % m
                    r = a[i + offset + p] % m
                    a[i + offset] = (l + r) % m
                    a[i + offset + p] = (m + l - r) * inow % m
                inow = sum_ie[self.bsf(~s)] * inow % m
        return a

    @staticmethod
    def resize(array: list, sz: int) -> list:
        new_array = array + [0] * (sz - len(array))
        return new_array
    @staticmethod
    def ceil_pow2(n: int) -> int:
        x = 0
        while (1 << x) < n: x += 1
        return x
    @staticmethod
    def bsf(n: int) -> int:
        return (n & -n).bit_length() - 1
    def inv(self, x: int):
        if self.__is_prime_constexpr():
            assert x
            return self.mypow(x, self.MOD - 2)
        else:
            eg = self.__inv_gcd(x)
            assert eg[0] == 1
            return eg[1]
    def mypow(self, x: int, n: int) -> int:
        assert 0 <= n
        r = 1
        while n:
            if n & 1: r = r * x % self.MOD
            x = x * x % self.MOD
            n >>= 1
        return r
    
    def __is_prime_constexpr(self) -> bool:
        n = self.MOD
        if n <= 1: return False
        if n == 2 or n == 7 or n == 61: return True
        if n % 2 == 0: return False
        d = n - 1
        while d % 2 == 0: d //= 2
        for a in [2, 7, 61]:
            t = d
            y = self.__pow_mod_constexpr(a, t, n)
            while t != n - 1 and y != 1 and y != n - 1:
                y = y * y % n
                t <<= 1
            if y != n - 1 and t % 2 == 0: return False
        return True
    def __pow_mod_constexpr(self, x: int, n: int, m: int) -> int:
        if m == 1: return 0
        _m = m; r = 1; y = self.__safe_mod(x, m)
        while n:
            if n & 1: r = (r * y) % _m
            y = (y * y) % _m
            n >>= 1
        return r
    def __safe_mod(self, x: int, m: int) -> int:
        x %= m
        if x < 0: x += m
        return x
    def __inv_gcd(self, a: int) -> tuple:
        b = self.MOD; a = safe_mod(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
            tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp
        if m0 < 0: m0 += b // s
        return (s, m0)
    def __primitive_root_constexpr(self) -> int:
        m = self.MOD
        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
        divs[0] = 2
        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 self.__pow_mod_constexpr(g, (m - 1) // divs[i], m) == 1:
                    ok = False
                    break
            if ok: return g
            g += 1







import sys









MOD = 998244353
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, m = read_ints()
    a = read_int_list()
    b = read_int_list()
    a = [x % MOD for x in a]
    b = [x % MOD for x in b]
    cnv = convolution(MOD)
    ans = cnv.convolution(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()

Solution (Python):



class convolution:
    def __init__(self, a: list, b: list, mod: int):
        self.a, self.b = a, b
        self.n, self.m = len(a), len(b)
        self.MOD = mod
        self.g = self.__primitive_root_constexpr()
    
    def convolution(self) -> list:
        n, m = self.n, self.m
        a, b = self.a, self.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] += a[i] * b[j] % self.MOD
                    ans[i + j] %= self.MOD
            return ans
        z = 1 << self.ceil_pow2(n + m - 1)
        a = self.resize(a, z)
        a = self.butterfly(a)
        b = self.resize(b, z)
        b = self.butterfly(b)
        for i in range(z): a[i] = a[i] * b[i] % self.MOD
        a = self.butterfly_inv(a)
        a = a[:n + m - 1]
        iz = self.inv(z)
        a = [x * iz % self.MOD for x in a]
        return a

    def butterfly(self, a: list) -> list:
        n = len(a)
        h = self.ceil_pow2(n)
        first = True
        sum_e = [0] * 30
        m = self.MOD
        if first:
            first = False
            es, ies = [0] * 30, [0] * 30
            cnt2 = self.bsf(m - 1)
            e = self.mypow(self.g, (m - 1) >> cnt2); ie = self.inv(e)
            for i in range(cnt2, 1, -1):
                es[i - 2] = e
                ies[i - 2] = ie
                e = e * e % m
                ie = ie * ie % m
            now = 1
            for i in range(cnt2 - 2):
                sum_e[i] = es[i] * now % m
                now = now * ies[i] % m
        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] % m
                    r = a[i + offset + p] * now % m
                    a[i + offset] = (l + r) % m
                    a[i + offset + p] = (l - r) % m
                now = now * sum_e[self.bsf(~s)] % m
        return a

    def butterfly_inv(self, a: list) -> list:
        n = len(a)
        h = self.ceil_pow2(n)        
        first = True
        sum_ie = [0] * 30
        m = self.MOD
        if first:
            first = False
            es, ies = [0] * 30, [0] * 30
            cnt2 = self.bsf(m - 1)
            e = self.mypow(self.g, (m - 1) >> cnt2); ie = self.inv(e)
            for i in range(cnt2, 1, -1):
                es[i - 2] = e
                ies[i - 2] = ie
                e = e * e % m
                ie = ie * ie % m
            now = 1
            for i in range(cnt2 - 2):
                sum_ie[i] = ies[i] * now % m
                now = es[i] * now % m
        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] % m
                    r = a[i + offset + p] % m
                    a[i + offset] = (l + r) % m
                    a[i + offset + p] = (m + l - r) * inow % m
                inow = sum_ie[self.bsf(~s)] * inow % m
        return a

    @staticmethod
    def resize(array: list, sz: int) -> list:
        new_array = array + [0] * (sz - len(array))
        return new_array
    @staticmethod
    def ceil_pow2(n: int) -> int:
        x = 0
        while (1 << x) < n: x += 1
        return x
    @staticmethod
    def bsf(n: int) -> int:
        return (n & -n).bit_length() - 1
    def inv(self, x: int):
        if self.__is_prime_constexpr():
            assert x
            return self.mypow(x, self.MOD - 2)
        else:
            eg = self.__inv_gcd(x)
            assert eg[0] == 1
            return eg[1]
    def mypow(self, x: int, n: int) -> int:
        assert 0 <= n
        r = 1
        while n:
            if n & 1: r = r * x % self.MOD
            x = x * x % self.MOD
            n >>= 1
        return r
    
    def __is_prime_constexpr(self) -> bool:
        n = self.MOD
        if n <= 1: return False
        if n == 2 or n == 7 or n == 61: return True
        if n % 2 == 0: return False
        d = n - 1
        while d % 2 == 0: d //= 2
        for a in [2, 7, 61]:
            t = d
            y = self.__pow_mod_constexpr(a, t, n)
            while t != n - 1 and y != 1 and y != n - 1:
                y = y * y % n
                t <<= 1
            if y != n - 1 and t % 2 == 0: return False
        return True
    def __pow_mod_constexpr(self, x: int, n: int, m: int) -> int:
        if m == 1: return 0
        _m = m; r = 1; y = self.__safe_mod(x, m)
        while n:
            if n & 1: r = (r * y) % _m
            y = (y * y) % _m
            n >>= 1
        return r
    def __safe_mod(self, x: int, m: int) -> int:
        x %= m
        if x < 0: x += m
        return x
    def __inv_gcd(self, a: int) -> tuple:
        b = self.MOD; a = safe_mod(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
            tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp
        if m0 < 0: m0 += b // s
        return (s, m0)
    def __primitive_root_constexpr(self) -> int:
        m = self.MOD
        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
        divs[0] = 2
        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 self.__pow_mod_constexpr(g, (m - 1) // divs[i], m) == 1:
                    ok = False
                    break
            if ok: return g
            g += 1







import sys









MOD = 998244353
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, m = read_ints()
    a = read_int_list()
    b = read_int_list()
    a = [x % MOD for x in a]
    b = [x % MOD for x in b]
    cnv = convolution(a, b, MOD)
    ans = cnv.convolution()
    print(*ans)

if __name__ == '__main__':
    Main()