#include <bits/stdc++.h>
namespace IOStream {
const int MAXR = 10000000;
char _READ_[MAXR], _PRINT_[MAXR];
int _READ_POS_, _PRINT_POS_, _READ_LEN_;
inline char readc() {
#ifndef ONLINE_JUDGE
return getchar();
#endif
if (!_READ_POS_) _READ_LEN_ = fread(_READ_, 1, MAXR, stdin);
char c = _READ_[_READ_POS_++];
if (_READ_POS_ == MAXR) _READ_POS_ = 0;
if (_READ_POS_ > _READ_LEN_) return 0;
return c;
}
template<typename T> inline void read(T &x) {
x = 0; register int flag = 1, c;
while (((c = readc()) < '0' || c > '9') && c != '-');
if (c == '-') flag = -1; else x = c - '0';
while ((c = readc()) >= '0' && c <= '9') x = x * 10 - '0' + c;
x *= flag;
}
template<typename T1, typename ...T2> inline void read(T1 &a, T2&... x) {
read(a), read(x...);
}
inline int reads(char *s) {
register int len = 0, c;
while (isspace(c = readc()) || !c);
s[len++] = c;
while (!isspace(c = readc()) && c) s[len++] = c;
s[len] = 0;
return len;
}
inline void ioflush() { fwrite(_PRINT_, 1, _PRINT_POS_, stdout), _PRINT_POS_ = 0; fflush(stdout); }
inline void printc(char c) {
if (!c) return;
_PRINT_[_PRINT_POS_++] = c;
if (_PRINT_POS_ == MAXR) ioflush();
}
inline void prints(const char *s, char c) {
for (int i = 0; s[i]; i++) printc(s[i]);
printc(c);
}
template<typename T> inline void print(T x, char c = '\n') {
if (x < 0) printc('-'), x = -x;
if (x) {
static char sta[20];
register int tp = 0;
for (; x; x /= 10) sta[tp++] = x % 10 + '0';
while (tp > 0) printc(sta[--tp]);
} else printc('0');
printc(c);
}
template<typename T1, typename ...T2> inline void print(T1 x, T2... y) {
print(x, ' '), print(y...);
}
}
using namespace IOStream;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int BIT = 20, MAXN = 1 << BIT;
namespace PolyMTT {
const int MOD = 1000000007;
const double PI = 3.14159265358979323846264;
int hasinit;
struct C {
double x, y;
C operator+(const C &a) const { return (C) { x + a.x, y + a.y }; }
C operator-(const C &a) const { return (C) { x - a.x, y - a.y }; }
C operator*(const C &a) const { return (C) { x * a.x - y * a.y, x * a.y + y * a.x }; }
} w[2][MAXN];
void init() {
hasinit = 1;
const int temp = 1 << BIT;
for (int i = 0; i < MAXN; i++) w[0][i] = (C) { cos(PI * 2 * i / temp), sin(PI * 2 * i / temp) };
for (int i = 0; i < MAXN; i++) w[1][i] = (C) { cos(PI * 2 * i / temp), -sin(PI * 2 * i / temp) };
}
void fft(C *a, int n, int rev) {
if (!hasinit) init();
for (int i = 0, j = 0; i < n; i++) {
if (i < j) swap(a[i], a[j]);
for (int k = n >> 1; (j ^= k) < k; k >>= 1);
}
static C ww[MAXN];
for (int h = 2; h <= n; h <<= 1) {
int hh = h >> 1, t = (1 << BIT) / h;
for (int i = 0; i < hh; i++) ww[i] = w[rev][i * t];
for (int i = 0; i < n; i += h) {
C *aj = a + i, *ah = aj + hh, *wn = ww;
for (int j = i; j < i + hh; ++j, ++aj, ++ah, ++wn) {
const C x = *aj, y = *ah * *wn;
*aj = x + y, *ah = x - y;
}
}
}
if (rev) for (int i = 0; i < n; i++) a[i].x /= n, a[i].y /= n;
}
void mtt(int *a, int *b, int *c, int n, int m, int p) {
if ((ll)n * m <= 4096) {
typedef unsigned long long ull;
static ull res[MAXN];
for (int i = 0; i < p; i++) res[i] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m && i + j < p; j++) res[i + j] += (ull)a[i] * b[j];
if (!(i & 15)) for (int j = 0; j < p; j++) res[j] %= MOD;
}
for (int i = 0; i < p; i++) c[i] = res[i] % MOD;
} else {
static C A[MAXN], B[MAXN], D[MAXN];
int len = 1; while (len < n + m - 1) len <<= 1;
for (int i = 0; i < len; i++) A[i] = B[i] = (C) { 0.0, 0.0 };
for (int i = 0; i < n; i++) A[i] = (C) { (double)(a[i] & 0x7FFF), (double)(a[i] >> 15) };
for (int i = 0; i < m; i++) B[i] = (C) { (double)(b[i] & 0x7FFF), (double)(b[i] >> 15) };
fft(A, len, 0), fft(B, len, 0);
for (int i = 0; i < len; i++) {
int j = (len - i) & (len - 1);
C ca = (C) { (A[i].x + A[j].x) * 0.5, (A[i].y - A[j].y) * 0.5 };
C cb = (C) { (B[i].x + B[j].x) * 0.5, (B[i].y - B[j].y) * 0.5 };
D[i] = ca * cb;
}
for (int i = 0; i < len; i++) A[i] = A[i] * B[i];
fft(A, len, 1), fft(D, len, 1);
for (int i = 0; i < p; i++) {
ll bd = (ll)round(D[i].x) % MOD + MOD, ac = (bd - (ll)round(A[i].x) % MOD + MOD) % MOD;
c[i] = ((ac << 30) + (((ll)round(A[i].y) % MOD + MOD) << 15) + bd) % MOD;
}
}
}
}
namespace PolyNTT {
const int MOD = 998244353, G = 3;
int w[2][MAXN], inv[MAXN], hasinit;//power table
int modpow(int a, int b) {
int res = 1;
for (; b; b >>= 1) {
if (b & 1) res = (ll)res * a % MOD;
a = (ll)a * a % MOD;
}
return res;
}
void init() {
hasinit = 1;
int mul = modpow(G, (MOD - 1) >> BIT);
for (int i = w[0][0] = 1; i < MAXN; i++) w[0][i] = (ll)w[0][i - 1] * mul % MOD;
mul = modpow(G, MOD - 1 - ((MOD - 1) >> BIT));
for (int i = w[1][0] = 1; i < MAXN; i++) w[1][i] = (ll)w[1][i - 1] * mul % MOD;
inv[1] = 1;
for (int i = 2; i < MAXN; i++) inv[i] = MOD - (ll)MOD / i * inv[MOD % i] % MOD;
}
int get_tpow(int n) {//return min{2^k|2^k>=n}
int k = 1;
while (k < n) k <<= 1;
return k;
}
void ntt(int *b, int n, int rev) {
if (!hasinit) init();
typedef unsigned long long ull;
static ull a[MAXN]; static int ww[MAXN];
const ull mmod = (ull)MOD * MOD; const int *W = w[rev];
for (int i = 0, j = 0; i < n; i++) {
a[j] = b[i];
for (int k = n >> 1; (j ^= k) < k; k >>= 1);
}
int n0 = __builtin_ctz(n);
if (n0 & 1) {
for (int i = 0; i < n; i += 2) {
const ull x = a[i], y = a[i + 1];
a[i] = x + y, a[i + 1] = x + MOD - y;
}
}
for (int h = n0 & 1 ? 4 : 2; h <= n; h <<= 2) {
int hh = h >> 1, t = (1 << BIT) / h >> 1;
for (int i = 0; i < h; i++) ww[i] = W[i * t];
for (int i = 0; i < n; i += h << 1) {
ull *ax = a + i, *ay = a + i + hh, *au = a + i + h, *av = a + i + h + hh;
register int *aw = ww, *bw = ww, *cw = ww + hh;
for (register int j = i; j < i + hh; ++j, ++ax, ++ay, ++au, ++av, aw += 2, ++bw, ++cw) {
const ull x = *ax, y = *ay % MOD * *aw, u = *au, v = *av % MOD * *aw;
const ull p = x + y, q = x + mmod - y, o = (u + v) % MOD * *bw, r = (u + mmod - v) % MOD * *cw;
*ax = p + o, *ay = q + r, *au = p + mmod - o, *av = q + mmod - r;
}
}
if (h == 65536 || h == 32768) for (int j = 0; j < n; j++) a[j] %= MOD;
}
for (int i = 0; i < n; i++) b[i] = a[i] % MOD;
if (rev) {
int inv = modpow(n, MOD - 2);
for (int i = 0; i < n; i++) b[i] = (ll)b[i] * inv % MOD;
}
}
//reset a polynomial to zero
void reset(int *a, int n) { memset(a, 0, sizeof(int) * n); }
//copy polynomial a to b
void copy(int *a, int *b, int n) { memcpy(b, a, sizeof(int) * n); }
//get multiplication of two polynomial in O(nlogn)
void get_mul(int *a, int *b, int *c, int n, int m, int p) {
if ((ll)n * m <= 4096) {
typedef unsigned long long ull;
static ull res[MAXN];
for (int i = 0; i < p; i++) res[i] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m && i + j < p; j++) res[i + j] += (ull)a[i] * b[j];
if (!(i & 15)) for (int j = 0; j < p; j++) res[j] %= MOD;
}
for (int i = 0; i < p; i++) c[i] = res[i] % MOD;
} else {
static int A[MAXN], B[MAXN];
int len = get_tpow(n + m - 1);
reset(A, len), reset(B, len);
copy(a, A, n), copy(b, B, m);
ntt(A, len, 0), ntt(B, len, 0);
for (int i = 0; i < len; i++) A[i] = (ll)A[i] * B[i] % MOD;
ntt(A, len, 1);
copy(A, c, p);
}
}
//get inverse in O(nlogn)
void get_inv(int *a, int *b, int n) {
static int ta[MAXN];
b[0] = modpow(a[0], MOD - 2), b[1] = 0;
for (int ii = 1; ii < n; ii <<= 1) {
int i = ii << 1, m = i << 1;
reset(ta + i, i), reset(b + i, i);
copy(a, ta, i);
ntt(ta, m, 0), ntt(b, m, 0);
for (int j = 0; j < m; j++) b[j] = (2LL - (ll)b[j] * ta[j] % MOD + MOD) * b[j] % MOD;
ntt(b, m, 1);
reset(b + i, i);
}
}
//get derivitive function in O(n)
void get_der(int *a, int *b, int n) {//b can equal with a
for (int i = 0; i < n - 1; i++) b[i] = (ll)a[i + 1] * (i + 1) % MOD;
b[n - 1] = 0;
}
//get primitive function in O(nlogn)
void get_pri(int *a, int *b, int n) {//b can equal with a
for (int i = n - 1; i > 0; i--) b[i] = (ll)a[i - 1] * inv[i] % MOD;
b[0] = 0;
}
//get ln in O(nlogn)
void get_ln(int *a, int *b, int n) {
static int tb[MAXN];
get_der(a, b, n);
get_inv(a, tb, n);
get_mul(b, tb, b, n, n, n);
get_pri(b, b, n);
}
//get exp in O(nlogn)
void get_exp(int *a, int *b, int n) {
static int ta[MAXN], tb[MAXN], tc[MAXN];
b[0] = tb[0] = 1, b[1] = tb[1] = 0;
for (int ii = 1; ii < n; ii <<= 1) {
int i = ii << 1, m = i << 1;
//get inverse b to tc
reset(ta + i, i), reset(tb + i, i), reset(tc + i, i);
copy(b, ta, i), copy(tb, tc, i);
ntt(ta, m, 0), ntt(tc, m, 0);
for (int j = 0; j < m; j++) tc[j] = (2LL - (ll)ta[j] * tc[j] % MOD + MOD) * tc[j] % MOD;
ntt(tc, m, 1), reset(tc + i, i);
//get ln b
get_der(b, ta, i), reset(ta + i, i);
get_mul(ta, tc, ta, i, i, i);
get_pri(ta, ta, i);
//get exp to b
for (int j = 0; j < i; j++) ta[j] = (!j - ta[j] + a[j] + MOD) % MOD;
get_mul(b, ta, b, i, i, i), reset(b + i, i);
if (i < n) { //get inverse b to tb
reset(ta + i, i), copy(b, ta, i);
ntt(ta, m, 0), ntt(tb, m, 0);
for (int j = 0; j < m; j++) tb[j] = (2LL - (ll)ta[j] * tb[j] % MOD + MOD) * tb[j] % MOD;
ntt(tb, m, 1), reset(tb + i, i);
}
}
}
//get divisor in O(nlogn)
void get_div(int *a, int *b, int *p, int n, int m) {//a=bp+r
if (n < m) return;
reverse(a, a + n), reverse(b, b + m);
int lp = n - m + 1, len = get_tpow(lp);
get_inv(b, p, len);
get_mul(p, a, p, lp, n, lp);
reverse(p, p + lp), reverse(a, a + n), reverse(b, b + m);
}
//get modular in O(nlogn)
void get_mod(int *a, int *b, int *r, int n, int m) {//a=bp+r
if (n < m) { copy(a, r, n); return; }
static int d[MAXN];
int lp = n - m + 1;
get_div(a, b, d, n, m);
get_mul(b, d, r, m, lp, m - 1);
for (int i = 0; i < m - 1; i++) r[i] = (a[i] - r[i] + MOD) % MOD;
}
//get divisor and modular in O(nlogn)
void get_div(int *a, int *b, int *p, int *r, int n, int m) {//a=bp+r
if (n < m) { copy(a, r, n); return; }
get_div(a, b, p, n, m);
int lp = n - m + 1;
get_mul(p, b, r, lp, m, m - 1);
for (int i = 0; i < m - 1; i++) r[i] = (a[i] - r[i] + MOD) % MOD;
}
//get power in O(nlogn)
void get_pow(int *a, int *b, int n, int m, int p) {//b=a^m MOD x^p
static int tc[MAXN], td[MAXN];
int t = 0;
reset(b, p);
while (t < n && !a[t]) ++t;
if ((ll)t * m >= n) return;
int inv = modpow(a[t], MOD - 2);
for (int i = t; i < n; i++) tc[i - t] = (ll)a[i] * inv % MOD;
int len = get_tpow(p - t * m);
get_ln(tc, td, len);
for (int i = 0; i < len; i++) td[i] = (ll)td[i] * m % MOD;
get_exp(td, b, len);
inv = modpow(a[t], m);
for (int i = p - 1; i >= t * m; i--) b[i] = (ll)b[i - t * m] * inv % MOD;
reset(b, t * m);
}
//get square root in O(nlogn) and make sure a[0]=1
void get_sqrt(int *a, int *b, int n) {
static int ta[MAXN];
if (n == 1) { b[0] = 1; b[1] = 0; return; }
get_sqrt(a, b, n >> 1);
get_inv(b, ta, n);
get_mul(a, ta, ta, n, n, n);
const int inv2 = (MOD + 1) / 2;
for (int i = 0; i < n; i++) b[i] = (ll)(b[i] + ta[i]) * inv2 % MOD;
}
//get evaluation of polynomial in O(nlog^2n)
void pre_eval(int *a, int store[][MAXN], int l, int r, int dep) {
if (l == r) { store[dep][l << 1] = MOD - a[l], store[dep][l << 1 | 1] = 1; return; }
int mid = (l + r) >> 1;
pre_eval(a, store, l, mid, dep + 1);
pre_eval(a, store, mid + 1, r, dep + 1);
get_mul(store[dep + 1] + (l << 1), store[dep + 1] + ((mid + 1) << 1), store[dep] + (l << 1), mid - l + 2, r - mid + 1, r - l + 2);
}
void cal_eval(int *a, int *ans, int store[][MAXN], int temp[][MAXN], int n, int l, int r, int dep) {
get_mod(a, store[dep] + (l << 1), temp[dep] + l, n, r - l + 2);
if (l == r) { ans[l] = temp[dep][l]; return; }
int mid = (l + r) >> 1;
cal_eval(temp[dep] + l, ans, store, temp, r - l + 1, l, mid, dep + 1);
cal_eval(temp[dep] + l, ans, store, temp, r - l + 1, mid + 1, r, dep + 1);
}
void get_eval(int *a, int *x, int *y, int n, int m) {//a(x[i])=y[i]
static int store[BIT][MAXN], temp[BIT][MAXN];
pre_eval(x, store, 0, m - 1, 0);
cal_eval(a, y, store, temp, n, 0, m - 1, 0);
}
//get interpolation in O(nlog^2n)
void cal_inter(int *val, int store[][MAXN], int temp[][MAXN], int n, int l, int r, int dep) {//a(x[i])=y[i]
if (l == r) { temp[dep][l] = val[l]; return; }
int mid = (l + r) >> 1;
cal_inter(val, store, temp, n, l, mid, dep + 1);
cal_inter(val, store, temp, n, mid + 1, r, dep + 1);
get_mul(store[dep + 1] + ((mid + 1) << 1), temp[dep + 1] + l, temp[dep] + l, r - mid + 1, mid - l + 1, r - l + 1);
get_mul(store[dep + 1] + (l << 1), temp[dep + 1] + mid + 1, temp[dep + 1] + l, mid - l + 2, r - mid, r - l + 1);
for (int i = l; i <= r; i++) temp[dep][i] = (temp[dep][i] + temp[dep + 1][i]) % MOD;
}
void get_inter(int *x, int *y, int *a, int n) {
static int store[BIT][MAXN], temp[BIT][MAXN], der[MAXN], val[MAXN];
pre_eval(x, store, 0, n - 1, 0);
get_der(store[0], der, n + 1);
cal_eval(der, val, store, temp, n, 0, n - 1, 0);
for (int i = 0; i < n; i++) val[i] = (ll)y[i] * modpow(val[i], MOD - 2) % MOD;
cal_inter(val, store, temp, n, 0, n - 1, 0);
for (int i = 0; i < n; i++) a[i] = temp[0][i];
}
}
using namespace PolyNTT;
namespace Solve1 {
const int MAXN = 1000005;
struct Edge { int to, next; } edge[MAXN << 1];
int sz[MAXN], head[MAXN], n, m, K, tot, all;
ll f[MAXN], g[MAXN], ans;
void addedge(int u, int v) {
edge[++tot] = (Edge) { v, head[u] };
head[u] = tot;
}
void dfs1(int u, int fa) {
sz[u] = 1;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == fa) continue;
dfs1(v, u);
sz[u] += sz[v];
g[u] += g[v] + sz[v];
}
g[u] %= MOD;
}
void dfs2(int u, int fa) {
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == fa) continue;
f[v] = (f[u] + g[u] - g[v] - sz[v] + all - sz[v]) % MOD;
ll t = (f[u] + g[u] - g[v] - sz[v]) % MOD;
ans = (sz[v] * (all - sz[v]) + ans) % MOD;
ans = (3LL * (sz[v] * t + (all - sz[v]) * g[v]) + ans) % MOD;
ans = (6LL * t % MOD * g[v] + ans) % MOD;
dfs2(v, u);
}
}
void solve() {
read(n, m, K);
for (int i = 1; i <= n; i++) head[i] = f[i] = g[i] = sz[i] = 0;
tot = ans = 0;
for (int i = 1; i <= m; i++) {
int u, v; read(u, v);
addedge(u, v);
addedge(v, u);
}
K = (ll)K * K % MOD * K % MOD;
ll sum = 0;
for (int i = 1; i <= n; i++) if (!sz[i]) {
dfs1(i, 0); all = sz[i];
dfs2(i, 0);
sum = ((ll)K * sz[i] % MOD * (n - sz[i]) + sum) % MOD;
}
print((ans + MOD + (MOD + 1) / 2 * sum) % MOD);
}
}
int f[MAXN], g[MAXN], n, m;
int main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
read(n,m);
for (int i = 0; i <= n; ++i) read(f[i]);
for (int i = 0; i <= m; ++i) read(g[i]);
get_mul(f, g, f, n+1, m+1, n+m+1);
for (int i = 0; i <= n+m+1; ++i) print(f[i],' ');
ioflush();
}