#include using namespace std; #ifdef LOCAL #include "debug.hpp" #else #define debug(...) 1 #endif using u64 = unsigned long long; struct xorshift { using u32 = uint32_t; u32 x = 123456789, y = 362436069, z = 521288629, w = 88675123; xorshift(u32 seed = 0) { z ^= seed; } u32 operator()() { u32 t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } }; unsigned long long modpow128(unsigned long long a, unsigned long long n, unsigned long long mod) { unsigned long long res = 1; while (n > 0) { if (n & 1) { res = (__uint128_t) res * a % mod; } a = (__uint128_t) a * a % mod; n >>= 1; } return res; } const vector primes_small = {2, 7, 61}; const vector primes_large = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; bool MillerRabin(long long n) { if (n == 1) { return false; } else if (n == 2) { return true; } else if (n % 2 == 0) { return false; } long long d = n - 1, s = 0; while (d % 2 == 0) { s++; d >>= 1; } vector primes = (n < 4759123141LL ? primes_small : primes_large); for (int p : primes) { if (p >= n) { break; } bool composite = true; __int128_t x = modpow128(p, d, n); composite &= (x != 1); for (int i = 0; i < s; i++) { composite &= (x != n - 1); x = (x * x) % n; } if (composite) { return false; } } return true; } long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } long long find_prime_factor(long long N) { if (~N & 1) { return 2; } if (MillerRabin(N)) { return N; } random_device seed_gen; xorshift rnd(seed_gen()); long long beg = 0; auto f = [&] (long long A, long long d) -> long long { return ((__int128_t) A * A + d) % N; }; while (1) { long long d = rnd(); long long x = ++beg, y = f(x, d); while (1) { long long p = gcd(N, abs(x - y)); if (p == 0 || p == N) { break; } if (p != 1) { return p; } x = f(x, d); y = f(f(y, d), d); } } } vector prime_factorize(long long N) { if (N == 1) return {}; long long p = find_prime_factor(N); if (p == N) { return {p}; } vector left = prime_factorize(p); vector right = prime_factorize(N / p); left.insert(left.end(), right.begin(), right.end()); sort(left.begin(), left.end()); return left; } long long primitive_root(long long p) { if (p == 2) return 1; if (p == 167772161) return 3; if (p == 469762049) return 3; if (p == 754974721) return 11; if (p == 998244353) return 3; vector v = prime_factorize(p - 1); v.erase(unique(v.begin(), v.end()), v.end()); random_device seed_gen; mt19937_64 mt(seed_gen()); while (1) { unsigned long long x = mt() % p; if (x == 0) { continue; } if (modpow128(x, p - 1, p) == 1) { bool ok = true; for (int i = 0; i < (int) v.size(); i++) { if (modpow128(x, (p - 1) / v[i], p) == 1) { ok = false; break; } } if (ok) { assert(modpow128(x, p - 1, p) == 1); return x; } } } } long long extgcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1, y = 0; return a; } long long d = extgcd(b, a % b, y, x); y -= a / b * x; return d; } long long mod_inv(long long a, long long m) { long long x, y; extgcd(a, m, x, y); return (m + x % m) % m; } long long Garner(vector R, vector M, long long mod) { assert(R.size() == M.size()); M.push_back(mod); vector coeffs((int) M.size(), 1), constants((int) M.size(), 0); for (int i = 0; i < (int) R.size(); i++) { long long v = (R[i] - constants[i]) * mod_inv(coeffs[i], M[i]) % M[i]; if (v < 0) { v += M[i]; } for (int j = i + 1; j < (int) M.size(); j++) { (constants[j] += coeffs[j] * v) %= M[j]; (coeffs[j] *= M[i]) %= M[j]; } } return constants.back(); } template struct modint { unsigned int v = 0; static constexpr long long mod() { return m; } static constexpr unsigned int umod() { return m; } unsigned int val() { return v; } modint() : v(0) {} modint(long long _v) { long long x = (long long)(_v % umod()); if (x < 0) { x += umod(); } v = (unsigned int) x; } modint operator+() const { return *this; } modint operator-() const { return modint() - *this; } modint(const modint &rhs) { v = rhs.v; } modint &operator+=(const modint &rhs) { v += rhs.v; if (v >= umod()) { v -= umod(); } return *this; } modint operator+(const modint &rhs) const { return modint(*this) += rhs; } modint &operator-=(const modint &rhs) { v -= rhs.v; if (v >= umod()) { v += umod(); } return *this; } modint operator-(const modint &rhs) const { return modint(*this) -= rhs; } modint &operator*=(const modint &rhs) { unsigned long long x = v; x *= rhs.v; v = (unsigned int) (x % umod()); return *this; } modint operator*(const modint &rhs) const { return modint(*this) *= rhs; } template modint pow(T n) const { modint x = *this, ret = 1; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } modint inv() const { return pow(umod() - 2); } modint &operator/=(const modint &rhs) { *this *= rhs.inv(); return *this; } modint operator/(const modint &rhs) const { return modint(*this) /= rhs; } friend istream &operator>>(istream &is, modint &v) { long long x; is >> x; v.v = x; return is; } friend ostream &operator<<(ostream &os, modint &v) { return os << v.v; } }; constexpr int md = 998244353; // constexpr int md = 1000000007; vector> fact, inv, inv_fact; void cominit(int MAX) { fact.resize(MAX + 1); inv.resize(MAX + 1); inv_fact.resize(MAX + 1); fact[0] = fact[1] = 1; inv_fact[0] = inv_fact[1] = 1; inv[1] = 1; for (int i = 2; i <= MAX; i++) { fact[i] = fact[i - 1] * i; inv[i] = -inv[md % i] * (modint) (md / i); inv_fact[i] = inv_fact[i - 1] * inv[i]; } } template modint Com(T n, T k) { assert(n < (int) fact.size() && k < (int) fact.size()); if (n < k) return 0; if (n < 0 || k < 0) return 0; return fact[n] * inv_fact[k] * inv_fact[n - k]; } template modint Per(T n, T k) { assert(n < (int) fact.size() && k < (int) fact.size()); if (n < k) return 0; if (n < 0 || k < 0) return 0; return fact[n] * inv_fact[n - k]; } using Mint = modint; template vector> ntt(vector> A, modint p_root) { int N = A.size(); vector bit(N); bit[0] = 0; int b = __builtin_ctz(N); // N = 1 << b for (int i = 0; i < b; i++) { int x = 1 << i, y = 1 << (b - 1 - i); for (int j = 0; j < (1 << i); j++) { bit[x + j] = bit[j] + y; } } vector> B(N); for (int i = 0; i < N; i++) { B[i] = A[bit[i]]; } for (int i = 1; i <= b; i++) { modint g = p_root.pow((modint::mod() - 1) >> i); for (int j = 0; j < N; j += (1 << i)) { modint om = 1; for (int k = 0; k < (1 << (i - 1)); k++) { modint x = B[j + k], y = B[j + k + (1 << (i - 1))] * om; B[j + k] = x + y; B[j + k + (1 << (i - 1))] = x - y; om *= g; } } } return B; } /* vector convolution998244353(vector A, vector B) { int N = (int) A.size(), M = (int) B.size(); int deg = 1; while (deg < N + M) { deg <<= 1; } Mint p_root = 3; A.resize(deg), B.resize(deg); A = ntt(A, p_root); B = ntt(B, p_root); for (int i = 0; i < deg; i++) { A[i] *= B[i]; } A = ntt(A, p_root.inv()); A.resize(N + M - 1); Mint deg_inv = Mint(deg).inv(); for (int i = 0; i < N + M - 1; i++) { A[i] *= deg_inv; } return A; } */ using u64 = unsigned long long; template vector> convolution(vector> A, vector> B) { int N = (int) A.size(), M = (int) B.size(); int deg = 1; while (deg < N + M) { deg <<= 1; } A.resize(deg), B.resize(deg); long long p_root = primitive_root(MOD); A = ntt(A, modint(p_root)); B = ntt(B, modint(p_root)); for (int i = 0; i < deg; i++) { A[i] *= B[i]; } A = ntt(A, modint(p_root).inv()); A.resize(N + M - 1); modint deg_inv = modint(deg).inv(); for (int i = 0; i < N + M - 1; i++) { A[i] *= deg_inv; } return A; } vector convolution_arbitrary_mod(vector &A, vector &B, u64 MOD) { static constexpr u64 MOD1 = 754974721; // 2^24 static constexpr u64 MOD2 = 167772161; // 2^25 static constexpr u64 MOD3 = 469762049; // 2^26 int N = A.size(), M = B.size(); vector> MA1(N), MB1(M); vector> MA2(N), MB2(M); vector> MA3(N), MB3(M); for (int i = 0; i < N; i++) { MA1[i] = A[i]; MA2[i] = A[i]; MA3[i] = A[i]; } for (int i = 0; i < M; i++) { MB1[i] = B[i]; MB2[i] = B[i]; MB3[i] = B[i]; } vector> MC1 = convolution(MA1, MB1); vector> MC2 = convolution(MA2, MB2); vector> MC3 = convolution(MA3, MB3); vector C(N + M - 1); for (int i = 0; i < N + M - 1; i++) { vector R = {MC1[i].val(), MC2[i].val(), MC3[i].val()}; vector M = {MOD1, MOD2, MOD3}; C[i] = Garner(R, M, MOD); } return C; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector A(N + 1); for (int i = 0; i < N + 1; i++) { cin >> A[i]; } int M; cin >> M; vector B(M + 1); for (int i = 0; i < M + 1; i++) { cin >> B[i]; } vector C = convolution_arbitrary_mod(A, B, 258280327); cout << N + M << '\n'; for (int i = 0; i < N + M + 1; i++) { cout << C[i] << " \n"[i == N + M]; } }