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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


# 998244353 = 119*2**23

mod = 998244353
primitive_root = 3  # mod の原始根
roots = [pow(primitive_root,(mod-1) >> i,mod) for i in range(24)]
inv_roots = [pow(r,mod-2,mod) for r in roots]
# roots[i] = 1 の 2**i 乗根、inv_roots[i] = 1 の 2**i 乗根の逆元


# 順番は変わる

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)  # A の次数を 2冪-1 にする
    B += [0]*(N-b)  # B の次数を 2冪-1 にする
    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))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


# https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp

def solve(inp):
    def bit_length(n):
        x = 0
        while 1 << x < n:
            x += 1
        return x

    def bit_scan_forward(n):
        x = 0
        while n & 1 == 0:
            n >>= 1
            x += 1
        return x

    def pow_mod(x, n, m):
        r = 1
        y = x % m
        while n:
            if n & 1:
                r = (r * y) % m
            y = y * y % m
            n >>= 1
        return r

    def get_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 = [2]
        x = (m - 1) // 2
        while x & 1 == 0:
            x >>= 1
        i = 3
        while i * i <= x:
            if x % i == 0:
                divs.append(i)
                x //= i
                while x % i == 0:
                    x //= i
            i += 2
        if x > 1:
            divs.append(x)
        g = 2
        while True:
            ok = True
            for d in divs:
                if pow_mod(g, (m - 1) // d, m) == 1:
                    ok = False
                    break
            if ok:
                return g

    def butterfly_prepare(mod, primitive_root):
        sum_e = np.zeros(30, np.int64)
        sum_ie = np.zeros(30, np.int64)
        es = np.zeros(30, np.int64)
        ies = np.zeros(30, np.int64)
        cnt2 = bit_scan_forward(mod - 1)
        e = pow_mod(primitive_root, (mod - 1) >> cnt2, mod)
        ie = pow_mod(e, mod - 2, 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_e = 1
        now_ie = 1
        for i in range(cnt2 - 1):
            sum_e[i] = es[i] * now_e % mod
            sum_ie[i] = ies[i] * now_ie % mod
            now_e = now_e * ies[i] % mod
            now_ie = now_ie * es[i] % mod
        return sum_e, sum_ie

    def butterfly(aaa, mod, sum_e):
        n = aaa.size
        h = bit_length(n)

        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 = aaa[i + offset]
                    r = aaa[i + offset + p] * now % mod
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = (l - r) % mod
                now = now * sum_e[bit_scan_forward(~s)] % mod

    def butterfly_inv(aaa, mod, sum_ie):
        n = aaa.size
        h = bit_length(n)

        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 = aaa[i + offset]
                    r = aaa[i + offset + p]
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = ((l - r) * inow) % mod
                inow = inow * sum_ie[bit_scan_forward(~s)] % mod

    def convolution(aaa, bbb, MOD):
        n = aaa.size
        m = bbb.size
        z = 1 << bit_length(n + m - 1)
        raaa = np.zeros(z, np.int64)
        rbbb = np.zeros(z, np.int64)
        raaa[:n] = aaa
        rbbb[:m] = bbb
        primitive_root = get_primitive_root(MOD)
        sum_e, sum_ie = butterfly_prepare(MOD, primitive_root)
        butterfly(raaa, MOD, sum_e)
        butterfly(rbbb, MOD, sum_e)
        ccc = raaa * rbbb % MOD
        butterfly_inv(ccc, MOD, sum_ie)
        iz = pow_mod(z, MOD - 2, MOD)
        result = ccc[:n + m - 1] * iz % MOD
        return result

    MOD = 998244353
    n = inp[0]
    m = inp[1]
    aaa = inp[2:2 + n]
    bbb = inp[2 + n:]
    ccc = convolution(aaa, bbb, MOD)
    return ccc


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(*ans)