#include <iostream>
#include <algorithm>
#include <functional>
using i32 = int;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
#define IL __inline__ __attribute__((always_inline))
#define RC(T, x) reinterpret_cast<T>(x)
namespace Setting
{
	constexpr u32 mod = 998244353;
	constexpr int sta_l_MB = 64;
	constexpr int Detail = 1;
}
namespace __qed
{
	constexpr u32 primitive_root_constexpr(u32 M)
	{
		u32 ed = 0, n = M - 1, d[11] = {};
		for (int i = 2; i * i <= n; i++)
		{
			if (n % i == 0)
			{
				d[ed++] = i;
				do
				{
					n /= i;
				} while (n % i == 0);
			}
		}
		if (n > 1)
		{
			d[ed++] = n;
		}
		for (u32 g = 2, r = 0;; ++g)
		{
			for (u32 i = 0; i < ed; ++i)
			{
				u32 b = (M - 1) / d[i], a = g;
				for (r = 1; b; b >>= 1, a = u64(a) * a % M)
				{
					if (b & 1)
					{
						r = u64(r) * a % M;
					}
				}
				if (r == 1)
				{
					break;
				}
			}
			if (r != 1)
			{
				return g;
			}
		}
	}
	constexpr int bceil(int x) { return 1 << (32 - __builtin_clz(x - 1)); }
	constexpr int bit_up(int x) { return 1 << (32 - __builtin_clz(x)); }
	constexpr int cro_32(int x) { return __builtin_ctz(~x); }
	constexpr bool ispow2(u64 x) { return (x & (x - 1)) == 0; }
}
namespace Stat_Info
{
	using Setting::Detail;
	i64 ntt_size;
	i64 fill0_size, copy_size, rev_size;
	size_t max_cost_sta_l;
	constexpr const char *Author = "QedDust413 & killer_joke";
	constexpr const char *Thanks = "negiizhao, chaihf, rogeryoungh, Qdedawsd2233, bh1234666, yosupo, Pulsating_Dust, KKKKa, qdc, and more.";
	template <typename Tf = std::ostream>
	void report(Tf &outf = std::clog)
	{
		outf << '\n';
		if constexpr (Detail <= 0)
		{
			outf << "Statistics are turned off.\n";
		}
		if constexpr (Detail > 0)
		{
			outf << "ntt_size:" << ntt_size << "\n";
		}
		if constexpr (Detail > 1)
		{
			outf << "fill0_size:" << fill0_size << " copy_size:" << copy_size << " rev_size:" << rev_size << "\nmax_cost_sta:" << (double(max_cost_sta_l) / double(1 << 20)) << "\n";
		}
		outf << std::endl;
	}
}
namespace mem_helper
{
	using namespace __qed;
	template <size_t align>
	void *to_align(void *mem)
	{
		static_assert(ispow2(align) && (align != 0));
		return RC(void *, (RC(u64, mem) + (align - 1)) & (-align));
	}
	template <size_t align>
	bool is_align(const void *mem)
	{
		static_assert(ispow2(align) && (align != 0));
		return (RC(u64, mem) & (align - 1)) == 0;
	}
	using Setting::sta_l_MB;
	char _mem[sta_l_MB << 20];
	void *now = _mem;
	struct pre_aloc
	{
		void *t;
		pre_aloc() { t = now; }
		~pre_aloc() { now = t; }
	};
	template <typename T, size_t align>
	T *AlocS(size_t n)
	{
		T *r = RC(T *, to_align<align>(now));
		now = r + n;
		if constexpr (Stat_Info::Detail > 1)
		{
			Stat_Info::max_cost_sta_l = std::max<size_t>(RC(char *, now) - _mem, Stat_Info::max_cost_sta_l);
		}
		return r;
	}
	template <size_t align>
	void *_alocH(size_t n)
	{
		constexpr size_t ptr_size = sizeof(void *), Extra = (align + ptr_size);
		void *base = std::malloc(n + Extra), *p = to_align<align>(RC(char *, base) + ptr_size);
		return RC(void **, p)[-1] = base, p;
	}
	template <typename T, size_t align>
	T *AlocH(size_t n) { return RC(T *, _alocH<align>(n * sizeof(T))); }
	void Freed(void *p) { std::free(RC(void **, p)[-1]); }
	template <typename T, size_t align>
	struct Trivial_Aligned_Allocator
	{
		static_assert(std::is_trivial<T>::value);
		typedef T value_type;
		T *allocate(std::size_t n) { return AlocH<T, align>(n); }
		template <class T1>
		struct rebind
		{
			using other = Trivial_Aligned_Allocator<T1, align>;
		};
		void deallocate(T *p, std::size_t n) { Freed(p); }
	};
}
namespace Montgo
{
	struct Mont32
	{
		u32 Mod, Mod2, Inv, NInv, R2;
		constexpr Mont32(u32 n) : Mod(n), Mod2(n << 1), Inv(1), NInv(), R2((-u64(n)) % n)
		{
			for (int i = 0; i < 5; ++i)
			{
				Inv *= 2 - n * Inv;
			}
			NInv = -Inv;
		}
		constexpr IL u32 reduce(u64 x) const { return (x + u64(u32(x) * NInv) * Mod) >> 32; }
		constexpr IL u32 reduce_s(u64 x) const
		{
			u32 r = (x >> 32) - ((u64(u32(x) * Inv) * Mod) >> 32);
			return r >> 31 ? r + Mod : r;
		}
		constexpr IL u32 mul(u32 x, u32 y) const { return reduce(u64(x) * y); }
		constexpr IL u32 mul_s(u32 x, u32 y) const { return reduce_s(u64(x) * y); }
		constexpr IL u32 In(u32 x) const { return mul(x, R2); }
		constexpr IL u32 In_s(u32 x) const { return mul_s(x, R2); }
		constexpr IL u32 Out(u32 x) const
		{
			u32 r = (x + (u64(x * NInv) * Mod)) >> 32;
			return __builtin_expect(r < Mod, 1) ? r : r - Mod;
		}
	};
}
namespace field_Z
{
	using Setting::mod;
	constexpr Montgo::Mont32 Space(mod);
	constexpr u32 mod2 = Space.Mod2;
	constexpr IL u32 shrink(u32 x) { return x >= mod ? x - mod : x; }
	constexpr IL u32 dilate2(u32 x) { return x >> 31 ? x + mod2 : x; }
	using Z = u32;
	constexpr bool isgood(Z x) { return x < mod2; }
	constexpr IL Z InZ(u32 x) { return Space.In(x); }
	constexpr IL Z InZs(u32 x) { return Space.In_s(x); }
	constexpr Z zero_Z(0), one_Z(InZs(1)), not_exist_Z(-1);
	constexpr IL u32 OutZ(Z x) { return Space.Out(x); }
	constexpr bool equalZ(Z x, Z y) { return shrink(x) == shrink(y); }
	namespace calc
	{
		constexpr IL Z addZ(Z x, Z y) { return dilate2(x + y - mod2); }
		constexpr IL Z subZ(Z x, Z y) { return dilate2(x - y); }
		constexpr IL Z mulZ(Z x, Z y) { return Space.mul(x, y); }
		constexpr Z powZ(Z a, u32 b, Z r = one_Z)
		{
			for (; b; a = mulZ(a, a), b >>= 1)
			{
				if (b & 1)
				{
					r = mulZ(r, a);
				}
			}
			return r;
		}
		constexpr IL Z invZ(Z x) { return powZ(x, mod - 2); }
		constexpr IL Z divZ(Z x, Z y) { return powZ(y, mod - 2, x); }
		template <bool strict = true>
		constexpr IL Z mulZs(Z x, Z y)
		{
			if constexpr (strict)
			{
				return Space.mul_s(x, y);
			}
			return mulZ(x, y);
		}
		constexpr Z negZ(Z x) { return (!x - 1) & (mod2 - x); }
		namespace extend_
		{
			constexpr Z absZ(Z x)
			{
				u32 r = OutZ(x);
				return InZs(std::min(r, mod - r));
			}
			constexpr Z legendre(Z x) { return powZ(x, (mod - 1) >> 1); }
			constexpr bool isQR(Z x) { return equalZ(legendre(x), one_Z); }
			constexpr Z sqrtZ(Z x)
			{
				if (!isQR(x))
				{
					return not_exist_Z;
				}
				Z a(1), I_mul(0);
				while (isQR(I_mul = subZ(mulZ(a, a), x)))
				{
					++a;
				}
				struct dZ
				{
					Z r, i;
					constexpr void Mul(dZ d, Z I_) { *this = {addZ(mulZ(r, d.r), mulZ(mulZ(I_, i), d.i)), addZ(mulZ(r, d.i), mulZ(i, d.r))}; }
				};
				dZ s = {a, one_Z}, r = {one_Z, zero_Z};
				for (u32 b = (mod + 1) >> 1; b; b >>= 1, s.Mul(s, I_mul))
				{
					if (b & 1)
					{
						r.Mul(s, I_mul);
					}
				}
				return absZ(r.r);
			}
		}
	}
	template <int fixes, bool strict = true>
	constexpr Z trans(Z x)
	{
		constexpr Z o = fixes > 0 ? calc::powZ(Space.R2, fixes) : calc::powZ(1, -fixes);
		return calc::mulZs<strict>(x, o);
	}
	template <bool strict = true>
	constexpr Z trans(Z x, int fixes) { return calc::mulZs<strict>(x, fixes > 0 ? calc::powZ(Space.R2, fixes) : calc::powZ(1, -fixes)); }
	namespace Const
	{
		constexpr Z _half = InZs((mod + 1) >> 1), _neghalf = InZs((mod - 1) >> 1), neg_one = InZs(mod - 1);
		constexpr Z img = calc::extend_::sqrtZ(neg_one), imgI = mod - img, _imghalf = calc::mulZs(_half, img);
	}
}
#pragma GCC target("avx2")
#include <immintrin.h>
#define VEC(sz, T) __attribute((vector_size(sz))) T
namespace SIMD
{
	using i32x8 = VEC(32, i32);
	using u32x8 = VEC(32, u32);
	using i64x4 = VEC(32, i64);
	using u64x4 = VEC(32, u64);
	using I256 = __m256i;
	constexpr IL u32x8 setu32x8(u32 x) { return (u32x8){x, x, x, x, x, x, x, x}; }
	template <int typ>
	IL u32x8 shuffle(const u32x8 &x) { return RC(u32x8, _mm256_shuffle_epi32(RC(I256, x), typ)); }
	template <int typ>
	IL u32x8 blend(const u32x8 &x, const u32x8 &y) { return RC(u32x8, _mm256_blend_epi32(RC(I256, x), RC(I256, y), typ)); }
	IL I256 swaplohi128(const I256 &x) { return _mm256_permute2x128_si256(x, x, 1); }
	IL u32x8 &x8(u32 *data) { return *RC(u32x8 *, data); }
	IL const u32x8 &x8(const u32 *data) { return *RC(const u32x8 *, data); }
	IL I256 loadu(const void *data) { return _mm256_loadu_si256(RC(const __m256i_u *, data)); }
	IL void storeu(const I256 &x, void *data) { return _mm256_storeu_si256(RC(__m256i_u *, data), x); }
	IL u64x4 fus_mul(const u32x8 &x, const u32x8 &y) { return RC(u64x4, _mm256_mul_epu32(RC(I256, x), RC(I256, y))); }
}
namespace field_Z
{
	using SIMD::setu32x8;
	using SIMD::u32x8;
	using SIMD::x8;
	using Zx8 = u32x8;
	constexpr u32x8 modx8 = setu32x8(mod), mod2x8 = setu32x8(mod2), NInvx8 = setu32x8(Space.NInv);
	constexpr Zx8 one_Zx8 = setu32x8(one_Z), zerox8 = setu32x8(0u);
	IL Zx8 dilate2x8(const Zx8 &x) { return x + (RC(Zx8, RC(SIMD::i32x8, x) < RC(SIMD::i32x8, zerox8)) & mod2x8); }
	IL Zx8 shrinkx8(const Zx8 &x) { return x - ((x >= modx8) & modx8); }
	namespace calc
	{
		using namespace SIMD;
		IL Zx8 addZx8(const Zx8 &x, const Zx8 &y) { return dilate2x8(x + y - mod2x8); }
		IL Zx8 subZx8(const Zx8 &x, const Zx8 &y) { return dilate2x8(x - y); }
		IL Zx8 mulZx8(const Zx8 &x, const Zx8 &y)
		{
			u32x8 z = (NInvx8 * x * y);
			return blend<0xaa>(RC(u32x8, (fus_mul(x, y) + fus_mul(z, modx8)) >> 32), RC(u32x8, (fus_mul(u32x8(u64x4(x) >> 32), u32x8(u64x4(y) >> 32)) + fus_mul(shuffle<0xf5>(z), modx8))));
		}
		IL Zx8 powZx8(const Zx8 &y, u32 b, const Zx8 &_r = one_Zx8)
		{
			Zx8 x = y, r = _r;
			for (; b; x = mulZx8(x, x), b >>= 1)
			{
				if (b & 1)
				{
					r = mulZx8(r, x);
				}
			}
			return r;
		}
		IL Zx8 invZx8(const Zx8 &x) { return powZx8(x, mod - 2); }
		IL Zx8 divZx8(const Zx8 &x, const Zx8 &y) { return powZx8(y, mod - 2, x); }
		template <bool strict = true>
		IL Zx8 mulZsx8(const Zx8 &x, const Zx8 &y)
		{
			if constexpr (strict)
			{
				u32x8 z = (NInvx8 * x * y);
				z = blend<0xaa>(RC(u32x8, (fus_mul(x, y) + fus_mul(z, modx8)) >> 32), RC(u32x8, (fus_mul(u32x8(u64x4(x) >> 32), u32x8(u64x4(y) >> 32)) + fus_mul(shuffle<0xf5>(z), modx8)))) - modx8;
				return z + (RC(Zx8, RC(i32x8, z) < RC(i32x8, zerox8)) & modx8);
			}
			return mulZx8(x, y);
		}
		IL Zx8 negZx8(const Zx8 &x) { return (x != zerox8) & (mod2x8 - x); }
		IL Zx8 _AmulZx8(const Zx8 &a, const Zx8 &b, const Zx8 &c) { return mulZx8(a + b, c); }
		IL Zx8 _SmulZx8(const Zx8 &a, const Zx8 &b, const Zx8 &c) { return mulZx8(a - b + mod2x8, c); }
	}
}
#undef VEC
#define STATI(ifo, dt, num)               \
	if constexpr (Stat_Info::Detail > dt) \
	{                                     \
		Stat_Info::ifo += (num);          \
	}
namespace poly
{
	namespace poly_base
	{
		using namespace field_Z;
		using __qed::bit_up;
		void fl0(Z *f, int l) { STATI(fill0_size, 1, l)
								std::fill_n(f, l, zero_Z); }
		void fl0(Z *bg, Z *ed) { STATI(fill0_size, 1, ed - bg)
								 std::fill(bg, ed, zero_Z); }
		void Cpy(const Z *f, int l, Z *g) { STATI(copy_size, 1, l)
											std::copy_n(f, l, g); }
		void Cpy(const Z *bg, const Z *ed, Z *g) { STATI(copy_size, 1, ed - bg)
												   std::copy(bg, ed, g); }
		void rev(Z *bg, Z *ed) { STATI(rev_size, 1, ed - bg)
								 std::reverse(bg, ed); }
		void rev(Z *f, int l) { STATI(rev_size, 1, l)
								std::reverse(f, f + l); }
		void Cpy_fl0(const Z *f, int n, Z *g, int lim) { Cpy(f, n, g), fl0(g + n, g + lim); }
		void Cpy_rev(const Z *f, int l, Z *g) { STATI(rev_size, 1, l)
												STATI(copy_size, 1, l) std::reverse_copy(f, f + l, g); }
		void mul_t_s(const Z *A, int l, Z *B, Z t)
		{
			int i = 0;
			if (l > 16)
			{
				Zx8 tx8 = setu32x8(t);
				for (; i + 7 < l; i += 8)
				{
					x8(B + i) = calc::mulZx8(x8(A + i), tx8);
				}
			}
			for (; i < l; ++i)
			{
				B[i] = calc::mulZ(A[i], t);
			}
		}
#define flx(nam, opt)                                         \
	void nam(Z *A, int l, const Z *B)                         \
	{                                                         \
		int i = 0;                                            \
		for (; i + 7 < l; i += 8)                             \
		{                                                     \
			x8(A + i) = calc::opt##Zx8(x8(A + i), x8(B + i)); \
		}                                                     \
		for (; i < l; ++i)                                    \
		{                                                     \
			A[i] = calc::opt##Z(A[i], B[i]);                  \
		}                                                     \
	}                                                         \
	void nam(const Z *A, const Z *B, int l, Z *C)             \
	{                                                         \
		int i = 0;                                            \
		for (; i + 7 < l; i += 8)                             \
		{                                                     \
			x8(C + i) = calc::opt##Zx8(x8(A + i), x8(B + i)); \
		}                                                     \
		for (; i < l; ++i)                                    \
		{                                                     \
			C[i] = calc::opt##Z(A[i], B[i]);                  \
		}                                                     \
	}
		flx(dot, mul) flx(addP, add) flx(subP, sub)
#undef flx
	}
	namespace poly_base
	{
		using mem_helper::pre_aloc;
		const std::function<Z *(size_t)> alocS = mem_helper::AlocS<Z, 32>;
		const std::function<Z *(size_t)> alocH = mem_helper::AlocH<Z, 32>;
		const std::function<void(void *)> freed = mem_helper::Freed;
	}
	using namespace poly_base;
}
namespace poly
{
	namespace f_n_t_t_base
	{
		using namespace calc;
		using __qed::cro_32;
		constexpr int base4thre = 16;
		template <bool strict = false>
		void mul_t(Z *A, int l, Z t)
		{
			for (int j = 0; j < l; ++j)
			{
				A[j] = mulZs<strict>(A[j], t);
			}
		}
		constexpr int mp2 = __builtin_ctz(mod - 1);
		constexpr Z _g(InZ(__qed::primitive_root_constexpr(mod)));
		struct P_R_Tab
		{
			Z t[mp2 + 1];
			constexpr P_R_Tab(Z G) : t()
			{
				t[mp2] = shrink(powZ(G, (mod - 1) >> mp2));
				for (int i = mp2 - 1; ~i; --i)
				{
					t[i] = mulZs(t[i + 1], t[i + 1]);
				}
			}
			constexpr Z operator[](int i) const { return t[i]; }
		};
		constexpr P_R_Tab rt1(_g), rt1_I(invZ(_g));
		template <int lim>
		struct omega_info_base2
		{
			Z o[lim >> 1];
			constexpr omega_info_base2(const P_R_Tab &Tb) : o()
			{
				o[0] = one_Z;
				for (int i = 0; (1 << i) < (lim >> 1); ++i)
				{
					o[1 << i] = Tb[i + 2];
				}
				for (int i = 1, l = lim >> 1; i < l; ++i)
				{
					o[i] = mulZ(o[i & (i - 1)], o[i & -i]);
				}
			}
			constexpr Z operator[](int i) const { return o[i]; }
		};
		const omega_info_base2<base4thre> w(rt1), wI(rt1_I);
		constexpr Zx8 powXx8(Z X)
		{
			Z X2 = mulZs(X, X), X3 = mulZs(X2, X), X4 = mulZs(X3, X), X5 = mulZs(X4, X), X6 = mulZs(X5, X), X7 = mulZs(X6, X);
			return (Zx8){one_Z, X, X2, X3, X4, X5, X6, X7};
		}
		struct ntt_info_base4x8
		{
			Z rt3[mp2 - 2], rt3_I[mp2 - 2];
			Zx8 rt4ix8[mp2 - 3], rt4ix8_I[mp2 - 3];
			constexpr ntt_info_base4x8() : rt3(), rt3_I(), rt4ix8(), rt4ix8_I()
			{
				Z pr = one_Z, pr_I = one_Z;
				for (int i = 0; i < mp2 - 2; ++i)
				{
					rt3[i] = mulZs(pr, rt1[i + 3]), rt3_I[i] = mulZs(pr_I, rt1_I[i + 3]);
					pr = mulZs(pr, rt1_I[i + 3]), pr_I = mulZs(pr_I, rt1[i + 3]);
				}
				pr = one_Z, pr_I = one_Z;
				for (int i = 0; i < mp2 - 3; ++i)
				{
					rt4ix8[i] = powXx8(mulZs(pr, rt1[i + 4])), rt4ix8_I[i] = powXx8(mulZs(pr_I, rt1_I[i + 4]));
					pr = mulZs(pr, rt1_I[i + 4]), pr_I = mulZs(pr_I, rt1[i + 4]);
				}
			}
		};
		template <int typ>
		IL u32x8 Neg(const u32x8 &x) { return blend<typ>(x, mod2x8 - x); }
	}
	namespace f_n_t_t
	{
		using namespace f_n_t_t_base;
		template <bool strict = false, int fixes = 0>
		void dif_base2(Z *A, int lim)
		{
			STATI(ntt_size, 0, lim);
			for (int L = lim >> 1, R = lim; L; L >>= 1, R >>= 1)
			{
				for (int i = 0, k = 0; i < lim; i += R, ++k)
				{
					for (int j = 0; j < L; ++j)
					{
						Z x = dilate2(A[i + j] - mod2), y = mulZ(w[k], A[i + j + L]);
						A[i + j] = x + y, A[i + j + L] = x - y + mod2;
					}
				}
			}
			if constexpr (fixes)
			{
				mul_t<strict>(A, lim, trans<fixes>(one_Z));
			}
			else
			{
				for (int j = 0; j < lim; ++j)
				{
					A[j] = dilate2(A[j] - mod2);
					if constexpr (strict)
					{
						A[j] = shrink(A[j]);
					}
				}
			}
		}
		template <bool strict = false, int fixes = 0>
		void dit_base2(Z *A, int lim)
		{
			STATI(ntt_size, 0, lim);
			for (int L = 1, R = 2; L < lim; L <<= 1, R <<= 1)
			{
				for (int i = 0, k = 0; i < lim; i += R, ++k)
				{
					for (int j = 0; j < L; ++j)
					{
						Z x = A[i + j], y = A[i + j + L];
						A[i + j] = addZ(x, y), A[i + j + L] = mulZ(x - y + mod2, wI[k]);
					}
				}
			}
			mul_t<strict>(A, lim, trans<fixes + 1>(mod - ((mod - 1) / lim)));
		}
		constexpr Zx8 imagx8 = setu32x8(rt1[2]), imag_Ix8 = setu32x8(rt1_I[2]);
		constexpr Z w38 = mulZs(rt1[2], rt1[3]), w38I = mulZs(rt1_I[2], rt1_I[3]);
		constexpr ntt_info_base4x8 iab4;
		template <bool strict = false, int fixes = 0>
		void dif_base4x8(Z *A, int lim)
		{
			STATI(ntt_size, 0, lim);
			int n = lim >> 3, L = n >> 1;
			Zx8 *f = RC(Zx8 *, A);
			if (__builtin_ctz(n) & 1)
			{
				for (int j = 0; j < L; ++j)
				{
					Zx8 x = f[j], y = f[j + L];
					f[j] = x + y, f[j + L] = x - y + mod2x8;
				}
				L >>= 1;
			}
			L >>= 1;
			for (int R = L << 2; L; L >>= 2, R >>= 2)
			{
				Z _r = one_Z, _r2 = one_Z, _r3 = one_Z;
				for (int i = 0, k = 0; i < n; i += R, ++k)
				{
					Zx8 r = setu32x8(_r), r2 = setu32x8(_r2), r3 = setu32x8(_r3);
					for (int j = 0; j < L; ++j)
					{
#define F(c) f[i + j + c * L]
						Zx8 f0 = dilate2x8(F(0) - mod2x8), f1 = mulZx8(F(1), r), f2 = mulZx8(F(2), r2), f3 = mulZx8(F(3), r3);
						Zx8 f1f3 = _SmulZx8(f1, f3, imagx8), f02 = addZx8(f0, f2), f13 = addZx8(f1, f3), f_02 = subZx8(f0, f2);
						F(0) = f02 + f13, F(1) = f02 - f13 + mod2x8, F(2) = f_02 + f1f3, F(3) = f_02 - f1f3 + mod2x8;
#undef F
					}
					_r = mulZs(_r, iab4.rt3[cro_32(k)]), _r2 = mulZs(_r, _r), _r3 = mulZs(_r2, _r);
				}
			}
			{
				constexpr Zx8 _r = setu32x8(trans<fixes>(one_Z)), pr2 = {one_Z, one_Z, one_Z, rt1[2], one_Z, one_Z, one_Z, rt1[2]}, pr4 = {one_Z, one_Z, one_Z, one_Z, one_Z, rt1[3], rt1[2], w38};
				Zx8 r = _r;
				for (int i = 0; i < n; ++i)
				{
					Zx8 &fi = f[i];
					fi = mulZx8(fi, r);
					fi = _AmulZx8(Neg<0xf0>(fi), RC(Zx8, swaplohi128(RC(I256, fi))), pr4);
					fi = _AmulZx8(Neg<0xcc>(fi), shuffle<0x4e>(fi), pr2);
					fi = addZx8(Neg<0xaa>(fi), shuffle<0xb1>(fi));
					if constexpr (strict)
					{
						fi = shrinkx8(fi);
					}
					r = mulZsx8(r, iab4.rt4ix8[cro_32(i)]);
				}
			}
		}
		template <bool strict = false, int fixes = 0>
		void dit_base4x8(Z *A, int lim)
		{
			STATI(ntt_size, 0, lim);
			int n = lim >> 3, L = 1;
			Zx8 *f = RC(Zx8 *, A);
			{
				constexpr Zx8 pr2 = {one_Z, one_Z, one_Z, rt1_I[2], one_Z, one_Z, one_Z, rt1_I[2]}, pr4 = {one_Z, one_Z, one_Z, one_Z, one_Z, rt1_I[3], rt1_I[2], w38I};
				Zx8 r = setu32x8(trans<fixes + 1>(mod - ((mod - 1) / lim)));
				for (int i = 0; i < n; ++i)
				{
					Zx8 &fi = f[i];
					fi = _AmulZx8(Neg<0xaa>(fi), shuffle<0xb1>(fi), pr2);
					fi = _AmulZx8(Neg<0xcc>(fi), shuffle<0x4e>(fi), pr4);
					fi = _AmulZx8(Neg<0xf0>(fi), RC(Zx8, swaplohi128(RC(I256, fi))), r);
					r = mulZsx8(r, iab4.rt4ix8_I[cro_32(i)]);
				}
			}
			for (int R = L << 2; L < (n >> 1); L <<= 2, R <<= 2)
			{
				Z _r = one_Z, _r2 = one_Z, _r3 = one_Z;
				for (int i = 0, k = 0; i < n; i += R, ++k)
				{
					Zx8 r = setu32x8(_r), r2 = setu32x8(_r2), r3 = setu32x8(_r3);
					for (int j = 0; j < L; ++j)
					{
#define F(c) f[i + j + c * L]
						Zx8 f0 = F(0), f1 = F(1), f2 = F(2), f3 = F(3);
						Zx8 f2f3 = _SmulZx8(f2, f3, imag_Ix8), f01 = addZx8(f0, f1), f23 = addZx8(f2, f3), f_01 = subZx8(f0, f1);
						F(0) = addZx8(f01, f23), F(1) = _AmulZx8(f_01, f2f3, r), F(2) = _SmulZx8(f01, f23, r2), F(3) = _SmulZx8(f_01, f2f3, r3);
#undef F
					}
					_r = mulZs(_r, iab4.rt3_I[cro_32(k)]), _r2 = mulZs(_r, _r), _r3 = mulZs(_r2, _r);
				}
			}
			if (__builtin_ctz(n) & 1)
			{
				for (int j = 0; j < L; ++j)
				{
					Zx8 x = f[j], y = f[j + L];
					f[j] = addZx8(x, y), f[j + L] = subZx8(x, y);
				}
			}
			if constexpr (strict)
			{
				for (int i = 0; i < n; ++i)
				{
					f[i] = shrinkx8(f[i]);
				}
			}
		}
		template <bool strict = false, int fixes = 0>
		void dif(Z *A, int lim) { lim >= base4thre ? dif_base4x8<strict, fixes>(A, lim) : dif_base2<strict, fixes>(A, lim); }
		template <bool strict = false, int fixes = 0>
		void dit(Z *A, int lim) { lim >= base4thre ? dit_base4x8<strict, fixes>(A, lim) : dit_base2<strict, fixes>(A, lim); }
	}
	using f_n_t_t::dif;
	using f_n_t_t::dit;
}
#undef STATI
#include <sys/mman.h>
#include <sys/stat.h>
#include <cstring>
namespace QIO_base
{
	constexpr int O_buffer_default_size = 1 << 18;
	constexpr int O_buffer_default_flush_threshold = 40;
	struct _int_to_char_tab
	{
		char tab[40000];
		constexpr _int_to_char_tab() : tab()
		{
			for (int i = 0; i != 10000; ++i)
			{
				for (int j = 3, n = i; ~j; --j)
				{
					tab[i * 4 + j] = n % 10 + 48, n /= 10;
				}
			}
		}
	} constexpr _otab;
}
namespace QIO_I
{
	using namespace QIO_base;
	struct Qinf
	{
		FILE *f;
		char *bg, *ed, *p;
		struct stat Fl;
		Qinf(FILE *fi) : f(fi)
		{
			int fd = fileno(f);
			fstat(fd, &Fl);
			bg = (char *)mmap(0, Fl.st_size + 1, PROT_READ, MAP_PRIVATE, fd, 0);
			p = bg, ed = bg + Fl.st_size;
			madvise(p, Fl.st_size + 1, MADV_SEQUENTIAL);
		}
		~Qinf() { munmap(bg, Fl.st_size + 1); }
		void skip_space()
		{
			while (*p <= ' ')
			{
				++p;
			}
		}
		char get() { return *p++; }
		char seek() { return *p; }
		bool eof() { return p == ed; }
		Qinf &read(char *s, size_t count) { return memcpy(s, p, count), p += count, *this; }
		Qinf &operator>>(u32 &x)
		{
			skip_space(), x = 0;
			for (; *p > ' '; ++p)
			{
				x = x * 10 + (*p & 0xf);
			}
			return *this;
		}
		Qinf &operator>>(int &x)
		{
			skip_space();
			if (*p == '-')
			{
				for (++p, x = 48 - *p++; *p > ' '; ++p)
				{
					x = x * 10 - (*p ^ 48);
				}
			}
			else
			{
				for (x = *p++ ^ 48; *p > ' '; ++p)
				{
					x = x * 10 + (*p ^ 48);
				}
			}
			return *this;
		}
	} qin(stdin);
}
namespace QIO_O
{
	using namespace QIO_base;
	struct Qoutf
	{
		FILE *f;
		char *bg, *ed, *p;
		char *ed_thre;
		int fp;
		u64 _fpi;
		Qoutf(FILE *fo, size_t sz = O_buffer_default_size) : f(fo), bg(new char[sz]), ed(bg + sz), p(bg), ed_thre(ed - O_buffer_default_flush_threshold), fp(6), _fpi(1000000ull) {}
		void flush() { fwrite_unlocked(bg, 1, p - bg, f), p = bg; }
		void chk()
		{
			if (__builtin_expect(p > ed_thre, 0))
			{
				flush();
			}
		}
		~Qoutf()
		{
			flush();
			delete[] bg;
		}
		void put4(u32 x)
		{
			if (x > 99u)
			{
				if (x > 999u)
				{
					memcpy(p, _otab.tab + (x << 2) + 0, 4), p += 4;
				}
				else
				{
					memcpy(p, _otab.tab + (x << 2) + 1, 3), p += 3;
				}
			}
			else
			{
				if (x > 9u)
				{
					memcpy(p, _otab.tab + (x << 2) + 2, 2), p += 2;
				}
				else
				{
					*p++ = x ^ 48;
				}
			}
		}
		void put2(u32 x)
		{
			if (x > 9u)
			{
				memcpy(p, _otab.tab + (x << 2) + 2, 2), p += 2;
			}
			else
			{
				*p++ = x ^ 48;
			}
		}
		Qoutf &write(const char *s, size_t count)
		{
			if (count > 1024 || p + count > ed_thre)
			{
				flush(), fwrite_unlocked(s, 1, count, f);
			}
			else
			{
				memcpy(p, s, count), p += count, chk();
			}
			return *this;
		}
		Qoutf &operator<<(char ch) { return *p++ = ch, *this; }
		Qoutf &operator<<(u32 x)
		{
			if (x > 99999999u)
			{
				put2(x / 100000000u), x %= 100000000u;
				memcpy(p, _otab.tab + ((x / 10000u) << 2), 4), p += 4;
				memcpy(p, _otab.tab + ((x % 10000u) << 2), 4), p += 4;
			}
			else if (x > 9999u)
			{
				put4(x / 10000u);
				memcpy(p, _otab.tab + ((x % 10000u) << 2), 4), p += 4;
			}
			else
			{
				put4(x);
			}
			return chk(), *this;
		}
		Qoutf &operator<<(int x)
		{
			if (x < 0)
			{
				*p++ = '-', x = -x;
			}
			return *this << static_cast<u32>(x);
		}
	} qout(stdout);
}
namespace QIO
{
	using QIO_I::qin;
	using QIO_I::Qinf;
	using QIO_O::qout;
	using QIO_O::Qoutf;
}
using namespace QIO;
void solve()
{
	int n, m;
	qin >> n >> m;
	int lim = __qed::bit_up(n + m - 2);
	auto F = poly::alocH(lim), G = poly::alocH(lim);
	for (int i = 0; i < n; ++i)
	{
		qin >> F[i];
	}
	std::fill(F + n, F + lim, 0);
	for (int i = 0; i < m; ++i)
	{
		qin >> G[i];
	}
	std::fill(G + m, G + lim, 0);
	poly::dif(F, lim), poly::dif(G, lim), poly::dot(F, lim, G), poly::dit<true, 1>(F, lim);
	for (int i = 0; i < n + m - 1; ++i)
	{
		qout << F[i] << ' ';
	}
	poly::freed(F), poly::freed(G);
}
int main()
{
	std::cin.tie(nullptr)->sync_with_stdio(false);
	solve();
	return 0;
}