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



Sample input:
4 5
1 2 3 4
5 6 7 8 9


Sample output:
5 16 34 60 70 70 59 36

Submission status: Runtime Error

Solution code:
# Date [ 2020-09-11 01:37:51 ]
# Problem [ f.py ]
# Author Koki_tkg
# とりあえずpythonに変換したけどバグだらけｗ
# 今の自分の力量ではここら辺が限界かも...後は上級者の翻訳待ち

# convolution.py
def butterfly(a: list):
    n = len(a)
    h = ceil_pow2(n)
    g = primitive_root(Mint.mod())
    
    first = True
    sum_e = [0] * 30
    if first:
        first = False
        es = [0] * 30; ies = [0] * 30
        cnt2 = bsf(Mint.mod() - 1)
        e = Mint(Mint(g).pow_((Mint.mod() - 1) >> cnt2)); ie = Mint(e.inv())
        for i in range(cnt2, 1, -1):
            es[i - 2] = e
            ies[i - 2] = ie
            e *= e
            ie *= ie
        now = Mint(1)
        for i in range(cnt2 - 2):
            sum_e[i] = es[i] * now
            now *= ies[i]
    for ph in range(1, h + 1):
        w = 1 << (ph - 1); p = 1 << (h - ph)
        now = Mint(1)
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = a[i + offset]
                r = a[i + offset + p] * now
                a[i + offset] = l + r
                a[i + offset + p] = l - r
            now *= sum_e[bsf(~s)]
    return a

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

def convolution_sub(a: list, b: list):
    n = len(a); m = len(b)
    if not n or not m: return []
    # using mint = static_modint<mod> ??
    a2 = [Mint(a[i]) for i in range(n)]
    b2 = [Mint(b[i]) for i in range(m)]

    c2 = convolution(a2, b2)
    c = [c2[i].val() for i in range(n + m - 1)]
    return c

# internal_math.py
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)

# modint.py
class Mint:
    modint1000000007 = 1000000007
    modint998244353 = 998244353

    def __init__(self, v: int = 0):
        # self.m = self.modint1000000007
        self.m = self.modint998244353
        self.x = v % self.__umod()
    
    def inv(self):
        if self.__is_prime_constexpr(self.__umod()):
            assert self.x
            return self.pow_(self.__umod() - 2)
        else:
            eg = self.__inv_gcd(self.x, self.m)
            assert eg[0] == 1
            return eg[2]

    def __str__(self): return str(self.x)
    
    def __iadd__(self, other):
        self.x += Mint.__get_val(other)
        if self.x >= self.__umod(): self.x -= self.__umod()
        return self
    def __add__(self, other):
        _v = Mint(self.x); _v += other
        return _v

    def __isub__(self, other):
        self.x -= Mint.__get_val(other)
        if self.x >= self.__umod(): self.x += self.__umod()
        return self
    def __sub__(self, other):
        _v = Mint(self.x); _v -= other
        return _v
    def __rsub__(self, other):
        _v = Mint(Mint.__get_val(other)); _v -= self
        return _v
    
    def __imul__(self, other):
        self.x =self.x * Mint.__get_val(other) % self.__umod()
        return self
    def __mul__(self, other):
        _v = Mint(self.x); _v *= other
        return _v

    def __itruediv__(self, other):
        self.x = self.x / Mint.__get_val(other) % self.__umod()
        return self
    def __truediv__(self, other):
        _v = Mint(self.x); _v /= other
        return _v
    def __rtruediv__(self, other):
        _v = Mint(Mint.__get_val(other)); _v /= self
        return _v
    
    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inv()
        return self
    def __floordiv__(self, other):
        _v = Mint(self.x); _v //= other
        return _v
    def __rfloordiv__(self, other):
        _v = Mint(Mint.__get_val(other)); _v //= self
        return _v

    def __pow__(self, other):
        _v = Mint(pow(self.x, Mint.__get_val(other), self.__umod()))
        return _v
    def __rpow__(self, other):
        _v = Mint(pow(Mint.__get_val(other), self.x, self.__umod()))
        return _v

    def __imod__(self, other):
        self.x %= Mint.__get_val(other)
        return self
    def __mod__(self, other):
        _v = Mint(self.x); _v %= other
        return _v
    def __rmod__(self, other):
        _v = Mint(Mint.__get_val(other)); _v %= self
        return _v

    def __ilshift__(self, other):
        self.x <<= Mint.__get_val(other)
        return self
    def __irshift__(self, other):
        self.x >>= Mint.__get_val(other)
        return self
    def __lshift__(self, other):
        _v = Mint(self.x); _v <<= other
        return _v
    def __rshift__(self, other):
        _v = Mint(self.x); _v >>= other
        return _v
    def __rlshift__(self, other):
        _v = Mint(Mint.__get_val(other)); _v <<= self
        return _v
    def __rrshift__(self, other):
        _v = Mint(Mint.__get_val(other)); _v >>= self
        return _v
    
    __repr__ = __str__
    __radd__ = __add__
    __rmul__ = __mul__

    def __umod(self): return self.m
    
    @staticmethod
    def __get_val(val): return val.x if isinstance(val, Mint) else val

    def __inv_gcd(self, a: int, b: int) -> tuple:
        a = self.__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)

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

    def __is_prime_constexpr(self, 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 = 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 pow_(self, n: int):
        assert n <= 0
        x = Mint(self.x); r = 1
        while n:
            if n & 1: r *= x
            x *= x
            n >>= 1
        return r
    def val(self): return self.x
    def mod(self): return self.m
    def raw(self, v):
        x = Mint()
        x.x = v
        return x

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

def bsf(n: int) -> int:
    count = 0
    while (n & 1) == 0:
        n >>= 1
        count += 1
    return count


import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
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()
    ans = convolution_sub(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()

Submission status: Runtime Error

Solution code:
# Date [ 2020-09-11 01:37:51 ]
# Problem [ f.py ]
# Author Koki_tkg
# とりあえずpythonに変換したけどバグだらけｗ
# 今の自分の力量ではここら辺が限界かも...後は上級者の翻訳待ち

# convolution.py
def butterfly(a: list):
    n = len(a)
    h = ceil_pow2(n)
    g = primitive_root(Mint.mod())
    
    first = True
    sum_e = [Mint()] * 30
    if first:
        first = False
        es = [Mint()] * 30; ies = [Mint()] * 30
        cnt2 = bsf(Mint.mod() - 1)
        e = Mint(Mint(g).pow_((Mint.mod() - 1) >> cnt2)); ie = Mint(e.inv())
        for i in range(cnt2, 1, -1):
            es[i - 2] = e
            ies[i - 2] = ie
            e *= e
            ie *= ie
        now = Mint(1)
        for i in range(cnt2 - 2):
            sum_e[i] = es[i] * now
            now *= ies[i]
    for ph in range(1, h + 1):
        w = 1 << (ph - 1); p = 1 << (h - ph)
        now = Mint(1)
        for s in range(w):
            offset = s << (h - ph + 1)
            for i in range(p):
                l = a[i + offset]
                r = a[i + offset + p] * now
                a[i + offset] = l + r
                a[i + offset + p] = l - r
            now *= sum_e[bsf(~s)]
    return a

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

def convolution_sub(a: list, b: list):
    n = len(a); m = len(b)
    if not n or not m: return []
    # using mint = static_modint<mod> ??
    a2 = [Mint(a[i]) for i in range(n)]
    b2 = [Mint(b[i]) for i in range(m)]

    c2 = convolution(a2, b2)
    c = [c2[i].val() for i in range(n + m - 1)]
    return c

# internal_math.py
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)

# modint.py
class Mint:
    modint1000000007 = 1000000007
    modint998244353 = 998244353

    def __init__(self, v: int = 0):
        # self.m = self.modint1000000007
        self.m = self.modint998244353
        self.x = v % self.__umod()
    
    def inv(self):
        if self.__is_prime_constexpr(self.__umod()):
            assert self.x
            return self.pow_(self.__umod() - 2)
        else:
            eg = self.__inv_gcd(self.x, self.m)
            assert eg[0] == 1
            return eg[2]

    def __str__(self): return str(self.x)
    
    def __iadd__(self, other):
        self.x += Mint.__get_val(other)
        if self.x >= self.__umod(): self.x -= self.__umod()
        return self
    def __add__(self, other):
        _v = Mint(self.x); _v += other
        return _v

    def __isub__(self, other):
        self.x -= Mint.__get_val(other)
        if self.x >= self.__umod(): self.x += self.__umod()
        return self
    def __sub__(self, other):
        _v = Mint(self.x); _v -= other
        return _v
    def __rsub__(self, other):
        _v = Mint(Mint.__get_val(other)); _v -= self
        return _v
    
    def __imul__(self, other):
        self.x =self.x * Mint.__get_val(other) % self.__umod()
        return self
    def __mul__(self, other):
        _v = Mint(self.x); _v *= other
        return _v

    def __itruediv__(self, other):
        self.x = self.x / Mint.__get_val(other) % self.__umod()
        return self
    def __truediv__(self, other):
        _v = Mint(self.x); _v /= other
        return _v
    def __rtruediv__(self, other):
        _v = Mint(Mint.__get_val(other)); _v /= self
        return _v
    
    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inv()
        return self
    def __floordiv__(self, other):
        _v = Mint(self.x); _v //= other
        return _v
    def __rfloordiv__(self, other):
        _v = Mint(Mint.__get_val(other)); _v //= self
        return _v

    def __pow__(self, other):
        _v = Mint(pow(self.x, Mint.__get_val(other), self.__umod()))
        return _v
    def __rpow__(self, other):
        _v = Mint(pow(Mint.__get_val(other), self.x, self.__umod()))
        return _v

    def __imod__(self, other):
        self.x %= Mint.__get_val(other)
        return self
    def __mod__(self, other):
        _v = Mint(self.x); _v %= other
        return _v
    def __rmod__(self, other):
        _v = Mint(Mint.__get_val(other)); _v %= self
        return _v

    def __ilshift__(self, other):
        self.x <<= Mint.__get_val(other)
        return self
    def __irshift__(self, other):
        self.x >>= Mint.__get_val(other)
        return self
    def __lshift__(self, other):
        _v = Mint(self.x); _v <<= other
        return _v
    def __rshift__(self, other):
        _v = Mint(self.x); _v >>= other
        return _v
    def __rlshift__(self, other):
        _v = Mint(Mint.__get_val(other)); _v <<= self
        return _v
    def __rrshift__(self, other):
        _v = Mint(Mint.__get_val(other)); _v >>= self
        return _v
    
    __repr__ = __str__
    __radd__ = __add__
    __rmul__ = __mul__

    def __umod(self): return self.m
    
    @staticmethod
    def __get_val(val): return val.x if isinstance(val, Mint) else val

    def __inv_gcd(self, a: int, b: int) -> tuple:
        a = self.__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)

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

    def __is_prime_constexpr(self, 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 = 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 pow_(self, n: int):
        assert n <= 0
        x = Mint(self.x); r = 1
        while n:
            if n & 1: r *= x
            x *= x
            n >>= 1
        return r
    def val(self): return self.x
    def mod(self): return self.m
    def raw(self, v):
        x = Mint()
        x.x = v
        return x

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

def bsf(n: int) -> int:
    count = 0
    while (n & 1) == 0:
        n >>= 1
        count += 1
    return count


import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
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()
    ans = convolution_sub(a, b)
    print(*ans)

if __name__ == '__main__':
    Main()