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






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

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

def inv(x, m):
    if is_prime_constexpr(m):
        assert x
        return pow_(x, m - 2)
    else:
        eg = inv_gcd(x, m)
        assert eg[0] == 1
        return eg[2]

def pow_(x, n: int):
    assert 0 <= n
    r = 1
    while n:
        if n & 1: r = r*x%MOD
        x = x*x%MOD
        n >>= 1
    return r

def inv_gcd(a: int, b: int) -> tuple:
    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 is_prime_constexpr(n: int) -> bool:
    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 = 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(x: int, n: int, m: int) -> int:
    if m == 1: return 0
    _m = m; r = 1; y = safe_mod(x, m)
    while n:
        if n & 1: r = (r * y) % _m
        y = (y * y) % _m
        n >>= 1
    return r


def safe_mod(x: int, m: int) -> int:
    x %= m
    if x < 0: x += m
    return x

class barrett:
    def __init__(self, m: int):
        self._m = m
        self.im = -1 // (m + 1)
    def umod(self): return self._m
    def mul(self, a: int, b: int) -> int:
        z = a
        z *= b
        x = (z * im) >> 64
        v = z - x * self._m
        if self._m <= v: v += self._m
        return v        

def pow_mod_constexpr(x: int, n: int, m: int) -> int:
    if m == 1: return 0
    _m = m; r = 1; y = safe_mod(x, m)
    while n:
        if n & 1: r = (r * y) % _m
        y = (y * y) % _m
        n >>= 1
    return r

def is_prime_constexpr(n: int) -> bool:
    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 = 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 is_prime(n: int) -> bool: return is_prime_constexpr(n)

def inv_gcd(self, a: int, b: int) -> tuple:
    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(m: int) -> int:
    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 pow_mod_constexpr(g, (m - 1) // div[i], m) == 1:
                ok = False
                break
        if ok: return g
        g += 1

def primitive_root(m: int) -> int: return primitive_root_constexpr(m)


def ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n: x += 1
    return x

def bsf(n: int) -> int:
    return (n & -n).bit_length() - 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]
    ans = convolution(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()

Solution (Python):
ROOT = 3
MOD = 998244353
pn = [pow(ROOT,(MOD-1)>>i,MOD) for i in range(30)]

def ntt_rec(a,n):
    if n==0:
        return a[:]
    if n==1:
        return [a[0]+a[1],a[0]-a[1]]

    b = ntt_rec(a[::2],n-1)
    c = ntt_rec(a[1::2],n-1)
    
    N = 1<<(n-1)
    res = [0]*(N*2)
    w_N = 1
    for k in range(N):
        res[k]   = (b[k] + w_N*c[k])%MOD
        res[k+N] = (b[k] - w_N*c[k])%MOD
        w_N = w_N*pn[n]%MOD
    return res

def intt_rec(a,n):
    res = ntt_rec(a[0:1]+a[1:][::-1],n)
    inv = pow(1<<n,MOD-2,MOD)
    for i in range(1<<n):
        res[i] = res[i]*inv%MOD
    return res


def convolution(a,b):
    deg = len(a) + len(b) - 1
    n = 0
    N = 1
    while deg*2 >= N:
        n += 1
        N <<= 1
    
    a += [0]*(N-len(a))
    b += [0]*(N-len(b))
    
    
    return intt_rec([ai*bi%MOD for ai,bi in zip(ntt_rec(a,n),ntt_rec(b,n))],n)

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))


L = len(a)+len(b)
c = convolution(a,b)
print(*c[:L-1])

Solution (Python):
class NTT:
    def __init__(self, convolution_rank, binary_level):
        self.cr = convolution_rank
        self.bl = binary_level
        self.modulo_list = [1]*convolution_rank
        self.primal_root_list = [1]*convolution_rank
        self.bin_list = [1]*(binary_level+1)
        self.primal_base_matrix = [[0 for _ in range(binary_level+1)] for __ in range(convolution_rank)]
        self.inverse_base_matrix = [[0 for _ in range(binary_level+1)] for __ in range(convolution_rank)]
        for i in range(binary_level):
            self.bin_list[i+1] = self.bin_list[i] * 2
    
    def doubling(self, n, m, modulo=0):
        y = 1
        tmp = m
        bas = n
        while tmp:
            if tmp % 2:
                y *= bas
                if modulo:
                    y %= modulo
            bas *= bas
            if modulo:
                bas %= modulo
            tmp >>= 1
        return y
    
    def powlimit(self, n):
        y = 1
        cnt = 0
        while y < n:
            y *= 2
            cnt += 1
        return y, cnt
    
    def IsPrime(self, num):
        p = 2
        if num <= 1:
            return False
        while p * p <= num:
            if num % p == 0:
                return False
            p += 1
        return True
    
    def extgcd(self, a, b, c):
        x, y, u, v, k, l = 1, 0, 0, 1, a, b
        while l:
            x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
            k, l = l, k % l
        if c % k:
            return "No Solution"
        return x * c, y * c
    
    def inved(self, a, modulo):
        x, y = self.extgcd(a, modulo, 1)
        return (x+modulo)%modulo
    
    def root_manual(self):
        for i in range(self.cr):
            r = 1
            flg = True
            while flg:
                fflg = True
                for j in range(self.bl):
                    if self.doubling(r, self.bin_list[j], self.modulo_list[i]) == 1:
                        fflg = False
                if self.doubling(r, self.bin_list[-1], self.modulo_list[i]) != 1:
                    fflg = False
                if fflg:
                    flg = False
                else:
                    r += 1
                    if r >= self.modulo_list[i]:
                        break
            self.primal_root_list[i] = r
    
    def make_prime_root(self):
        cnt = 0
        j = 1
        last = self.bin_list[-1]
        while cnt < self.cr:
            if self.IsPrime(j*last+1):
                flg = True
                r = 1
                while flg:
                    fflg = True
                    for i in range(self.bl):
                        if self.doubling(r, self.bin_list[i], j*last+1) == 1:
                            fflg = False
                    if self.doubling(r, last, j*last+1) != 1:
                        fflg = False
                    if fflg:
                        flg = False
                    else:
                        r += 1
                        if r >= j*last+1:
                            break
                if flg==False:
                    self.modulo_list[cnt] = j*last+1
                    self.primal_root_list[cnt] = r
                    cnt += 1
            j += 2
    
    def make_basis(self):
        for i in range(self.cr):
            for j in range(self.bl):
                tmp = self.doubling(2, self.bl-j)
                self.primal_base_matrix[i][j] = self.doubling(self.primal_root_list[i], tmp, self.modulo_list[i])
                self.inverse_base_matrix[i][j] = self.inved(self.primal_base_matrix[i][j], self.modulo_list[i])
    
    def NTT(self, f, n, idx, depth, inverse=False, surface=True):
        mod = self.modulo_list[idx]
        i2 = self.inved(2, mod)
        if inverse:
            seed = self.primal_base_matrix[idx][depth]
        else:
            seed = self.inverse_base_matrix[idx][depth]
        if n == 1:
            return f
        if n == 2:
            xf = [(f[0] + f[1])%mod, (f[0] - f[1])%mod]
            if inverse * surface:
                xf[0] *= i2
                xf[0] %= mod
                xf[1] *= i2
                xf[1] %= mod
            return xf
        hn = n // 2
        fe = [f[2*i+0] for i in range(hn)]
        fo = [f[2*i+1] for i in range(hn)]
        fe = self.NTT(fe, hn, idx, depth-1, inverse, False)
        fo = self.NTT(fo, hn, idx, depth-1, inverse, False)
        xf = [0 for _ in range(n)]
        grow = 1
        for i in range(hn):
            right = (fo[i] * grow) % mod
            xf[i+0*hn] = (fe[i] + right) % mod
            xf[i+1*hn] = (fe[i] - right) % mod
            grow *= seed
            grow %= mod
        if inverse * surface:
            invn = self.inved(n, mod)
            for i in range(n):
                xf[i] *= invn
                xf[i] %= mod
        return xf
    
    def second_NTT(self, f, n, idx, depth, inverse=False):
        res = [0 for _ in range(n)]
        tmp = [0 for _ in range(n)]
        MOD = self.modulo_list[idx]
        ipl = self.inved(n, MOD)
        for i in range(n):
            bas = 1
            pos = 0
            for j in range(depth, 0, -1):
                pos += bas * ((i>>(j-1)) % 2)
                bas *= 2
            res[i] = f[pos]
        for i in range(depth):
            grow = 1
            seed = inverse * self.primal_base_matrix[idx][i+1] + (1 - inverse) * self.inverse_base_matrix[idx][i+1]
            for k in range(1<<i):
                for j in range(1<<(depth-i-1)):
                    tmp[j*(1<<(i+1))+k+0*(1<<i)] = (res[j*(1<<(i+1))+k] + grow * res[j*(1<<(i+1))+k+(1<<i)]) % MOD
                    tmp[j*(1<<(i+1))+k+1*(1<<i)] = (res[j*(1<<(i+1))+k] - grow * res[j*(1<<(i+1))+k+(1<<i)]) % MOD
                grow *= seed
                grow %= MOD
            for j in range(n):
                res[j] = tmp[j]
        if inverse:
            for i in range(n):
                res[i] *= ipl
                res[i] %= MOD
        return res
    def CRT(self, num, a_list, m_list):
        r = a_list[0]
        bas = m_list[0]
        x, y = 0, 0
        for i in range(1, num):
            x, y = self.extgcd(bas, -m_list[i], -a_list[i]-r)
            r += bas * x
            bas *= m_list[i]
        return r % bas

N, M = map(int, input().split())
ntt = NTT(1, 23)
ntt.modulo_list[0] = 998244353
ntt.root_manual()
ntt.make_basis()
A = list(map(int, input().split()))
B = list(map(int, input().split()))
pl, cnt = ntt.powlimit(N+M)
A = A[:] + [0 for _ in range(pl-N)]
B = B[:] + [0 for _ in range(pl-M)]
X = ntt.second_NTT(A, pl, 0, cnt)
Y = ntt.second_NTT(B, pl, 0, cnt)
Z = [X[i]*Y[i]%ntt.modulo_list[0] for i in range(pl)]
Z = ntt.second_NTT(Z, pl, 0, cnt, True)
for i in range(N+M-1):
    print(Z[i], end = ' '*(i!=N+M-2))
print()

Solution (Python):
class NTT:
    def __init__(self, convolution_rank, binary_level):
        self.cr = convolution_rank
        self.bl = binary_level
        self.modulo_list = [1]*convolution_rank
        self.primal_root_list = [1]*convolution_rank
        self.bin_list = [1]*(binary_level+1)
        self.primal_base_matrix = [[0 for _ in range(binary_level+1)] for __ in range(convolution_rank)]
        self.inverse_base_matrix = [[0 for _ in range(binary_level+1)] for __ in range(convolution_rank)]
        for i in range(binary_level):
            self.bin_list[i+1] = self.bin_list[i] * 2
    
    def doubling(self, n, m, modulo=0):
        y = 1
        tmp = m
        bas = n
        while tmp:
            if tmp % 2:
                y *= bas
                if modulo:
                    y %= modulo
            bas *= bas
            if modulo:
                bas %= modulo
            tmp >>= 1
        return y
    
    def powlimit(self, n):
        y = 1
        cnt = 0
        while y < n:
            y *= 2
            cnt += 1
        return y, cnt
    
    def IsPrime(self, num):
        p = 2
        if num <= 1:
            return False
        while p * p <= num:
            if num % p == 0:
                return False
            p += 1
        return True
    
    def extgcd(self, a, b, c):
        x, y, u, v, k, l = 1, 0, 0, 1, a, b
        while l:
            x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
            k, l = l, k % l
        if c % k:
            return "No Solution"
        return x * c, y * c
    
    def inved(self, a, modulo):
        x, y = self.extgcd(a, modulo, 1)
        return (x+modulo)%modulo
    
    def root_manual(self):
        for i in range(self.cr):
            r = 1
            flg = True
            while flg:
                fflg = True
                for j in range(self.bl):
                    if self.doubling(r, self.bin_list[j], self.modulo_list[i]) == 1:
                        fflg = False
                if self.doubling(r, self.bin_list[-1], self.modulo_list[i]) != 1:
                    fflg = False
                if fflg:
                    flg = False
                else:
                    r += 1
                    if r >= self.modulo_list[i]:
                        break
            self.primal_root_list[i] = r
    
    def make_prime_root(self):
        cnt = 0
        j = 1
        last = self.bin_list[-1]
        while cnt < self.cr:
            if self.IsPrime(j*last+1):
                flg = True
                r = 1
                while flg:
                    fflg = True
                    for i in range(self.bl):
                        if self.doubling(r, self.bin_list[i], j*last+1) == 1:
                            fflg = False
                    if self.doubling(r, last, j*last+1) != 1:
                        fflg = False
                    if fflg:
                        flg = False
                    else:
                        r += 1
                        if r >= j*last+1:
                            break
                if flg==False:
                    self.modulo_list[cnt] = j*last+1
                    self.primal_root_list[cnt] = r
                    cnt += 1
            j += 2
    
    def make_basis(self):
        for i in range(self.cr):
            for j in range(self.bl):
                tmp = self.doubling(2, self.bl-j)
                self.primal_base_matrix[i][j] = self.doubling(self.primal_root_list[i], tmp, self.modulo_list[i])
                self.inverse_base_matrix[i][j] = self.inved(self.primal_base_matrix[i][j], self.modulo_list[i])
    
    def NTT(self, f, n, idx, depth, inverse=False, surface=True):
        mod = self.modulo_list[idx]
        i2 = self.inved(2, mod)
        if inverse:
            seed = self.primal_base_matrix[idx][depth]
        else:
            seed = self.inverse_base_matrix[idx][depth]
        if n == 1:
            return f
        if n == 2:
            xf = [(f[0] + f[1])%mod, (f[0] - f[1])%mod]
            if inverse * surface:
                xf[0] *= i2
                xf[0] %= mod
                xf[1] *= i2
                xf[1] %= mod
            return xf
        hn = n // 2
        fe = [f[2*i+0] for i in range(hn)]
        fo = [f[2*i+1] for i in range(hn)]
        fe = self.NTT(fe, hn, idx, depth-1, inverse, False)
        fo = self.NTT(fo, hn, idx, depth-1, inverse, False)
        xf = [0 for _ in range(n)]
        grow = 1
        for i in range(hn):
            right = (fo[i] * grow) % mod
            xf[i+0*hn] = (fe[i] + right) % mod
            xf[i+1*hn] = (fe[i] - right) % mod
            grow *= seed
            grow %= mod
        if inverse * surface:
            invn = self.inved(n, mod)
            for i in range(n):
                xf[i] *= invn
                xf[i] %= mod
        return xf
    
    def second_NTT(self, f, n, idx, depth, inverse=False):
        res = [0 for _ in range(n)]
        tmp = [0 for _ in range(n)]
        MOD = self.modulo_list[idx]
        ipl = self.inved(n, MOD)
        for i in range(n):
            bas = 1
            pos = 0
            for j in range(depth, 0, -1):
                pos += bas * ((i>>(j-1)) % 2)
                bas *= 2
            res[i] = f[pos]
        for i in range(depth):
            for j in range(1<<(depth-i-1)):
                grow = 1
                seed = inverse * self.primal_base_matrix[idx][i+1] + (1 - inverse) * self.inverse_base_matrix[idx][i+1]
                for k in range(1<<i):
                    tmp[j*(1<<(i+1))+k+0*(1<<i)] = (res[j*(1<<(i+1))+k] + grow * res[j*(1<<(i+1))+k+(1<<i)]) % MOD
                    tmp[j*(1<<(i+1))+k+1*(1<<i)] = (res[j*(1<<(i+1))+k] - grow * res[j*(1<<(i+1))+k+(1<<i)]) % MOD
                    grow *= seed
                    grow %= MOD
            for j in range(n):
                res[j] = tmp[j]
        if inverse:
            for i in range(n):
                res[i] *= ipl
                res[i] %= MOD
        return res
    def CRT(self, num, a_list, m_list):
        r = a_list[0]
        bas = m_list[0]
        x, y = 0, 0
        for i in range(1, num):
            x, y = self.extgcd(bas, -m_list[i], -a_list[i]-r)
            r += bas * x
            bas *= m_list[i]
        return r % bas

N, M = map(int, input().split())
ntt = NTT(1, 23)
ntt.modulo_list[0] = 998244353
ntt.root_manual()
ntt.make_basis()
A = list(map(int, input().split()))
B = list(map(int, input().split()))
pl, cnt = ntt.powlimit(N+M)
A = A[:] + [0 for _ in range(pl-N)]
B = B[:] + [0 for _ in range(pl-M)]
X = ntt.second_NTT(A, pl, 0, cnt)
Y = ntt.second_NTT(B, pl, 0, cnt)
Z = [X[i]*Y[i]%ntt.modulo_list[0] for i in range(pl)]
Z = ntt.second_NTT(Z, pl, 0, cnt, True)
for i in range(N+M-1):
    print(Z[i], end = ' '*(i!=N+M-2))
print()

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    mod=998244353
    
    class NTT:
        def __init__(self, MOD = 998244353, pr = 3, LS = 20):
            self.MOD = MOD
            self.N0 = 1<<LS
            omega = pow(pr, (MOD-1)//self.N0, MOD)
            omegainv = pow(omega, MOD-2, MOD)
            self.w = [0]*(self.N0//2)
            self.winv = [0]*(self.N0//2)
            self.w[0] = 1
            self.winv[0] = 1
            for i in range(1, self.N0//2):
                self.w[i] = (self.w[i-1]*omega)%MOD
                self.winv[i] = (self.winv[i-1]*omegainv)%MOD
            used = set()
            for i in range(self.N0//2):
                if i in used:
                    continue
                j = 0
                for k in range(LS-1):
                    j |= (i>>k&1) << (LS-2-k)
                used.add(j)
                self.w[i], self.w[j] = self.w[j], self.w[i]
                self.winv[i], self.winv[j] = self.winv[j], self.winv[i]
            
        def _fft(self, A):
            MOD = self.MOD
            M = len(A)
            bn = 1
            hbs = M>>1
            while hbs:
                for j in range(hbs):
                    A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                    if A[j] > MOD:
                        A[j] -= MOD
                    if A[j+hbs] < 0:
                        A[j+hbs] += MOD
                for bi in range(1, bn):
                    wi = self.w[bi]
                    for j in range(bi*hbs*2, bi*hbs*2+hbs):
                        A[j], A[j+hbs] = (A[j] + wi*A[j+hbs])%MOD, (A[j] - wi*A[j+hbs])%MOD
                bn <<= 1
                hbs >>= 1
    
        def _ifft(self, A):
            MOD = self.MOD
            M = len(A)
            bn = M>>1
            hbs = 1
            while bn:
                for j in range(hbs):
                    A[j], A[j+hbs] = A[j] + A[j+hbs], A[j] - A[j+hbs]
                    if A[j] > MOD:
                        A[j] -= MOD
                    if A[j+hbs] < 0:
                        A[j+hbs] += MOD
                for bi in range(1, bn):
                    winvi = self.winv[bi]
                    for j in range(bi*hbs*2, bi*hbs*2+hbs):
                        A[j], A[j+hbs] = (A[j] + A[j+hbs])%MOD, winvi*(A[j] - A[j+hbs])%MOD
                bn >>= 1
                hbs <<= 1
        
        def convolve(self, A, B):
            LA = len(A)
            LB = len(B)
            LC = LA+LB-1
            M = 1<<(LC-1).bit_length()
            A += [0]*(M-LA)
            B += [0]*(M-LB)
            self._fft(A)
            self._fft(B)
            C = [0]*M
            for i in range(M):
                C[i] = A[i]*B[i]%self.MOD
            self._ifft(C)
            minv = pow(M, self.MOD-2, self.MOD)
            for i in range(LC):
                C[i] = C[i]*minv%self.MOD
            return C[:LC]
            
            return C
        
        def inverse(self, A):
            LA = len(A)
            dep = (LA-1).bit_length()
            M = 1<<dep
            A += [0]*(M-LA)
            
            g = [pow(A[0], self.MOD-2, self.MOD)]
            for n in range(dep):
                dl = 1<<(n+1)
                f = A[:dl]
                fg = self.convolve(f, g[:])[:dl]
                fgg = self.convolve(fg, g[:])[:dl]
                ng = [None]*dl
                for i in range(dl//2):
                    ng[i] = (2*g[i]-fgg[i])%self.MOD
                for i in range(dl//2, dl):
                    ng[i] = self.MOD-fgg[i]
                g = ng[:]
            return g[:LA]



    
    N,M=map(int, input().split())
    A=list(map(int, input().split()))
    B=list(map(int, input().split()))
    
    ntt=NTT()
    C=ntt.convolve(A,B)
    ans=[]
    
    for c in C:
        ans.append(c)
        
    print(' '.join(map(str, C)))
    

main()