#include using namespace std; #include using namespace atcoder; #define int long long // #define endl "\n" #pragma GCC optimize("-O3") void solve(); typedef long long ll; typedef __int128_t LL; typedef unsigned long long ull; typedef double db; typedef long double ld; typedef pair pi; typedef pair> pip; typedef vector vi; typedef vector vd; typedef vector vb; typedef vector vs; typedef vector vc; typedef vector> vp; typedef vector> vvi; typedef vector> vvd; typedef vector> vvb; typedef vector> vvs; typedef vector> vvc; typedef vector>> vvp; typedef vector>> vvvi; typedef vector>>> vvvvi; template using vec = vector; template using vv = vector>; template using vvv = vector>>; template using vvvv = vector>>>; template using pq = priority_queue; template using pqg = priority_queue, greater>; template using mset = multiset; template using uset = unordered_set; template using umap = unordered_map; #define _PI 3.14159265358979323846 #define _E 2.7182818284590452354 #define fi first #define se second #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define td typedef #define elif else if #define ifnot(x) if(!(x)) #define all(obj) (obj).begin(), (obj).end() #define rall(obj) (obj).rbegin(), (obj).rend() #define sumv(a) accumulate(all(a), 0LL) #define lb(v, a) (lower_bound(begin(v), end(v), a) - begin(v)) #define ub(v, a) (upper_bound(begin(v), end(v), a) - begin(v)) #define inr(l, x, r) (l <= x && x < r) #define cbit(x) __builtin_popcountll(x) #define topbit(t) (t == 0 ? -1 : 63 - __builtin_clzll(t)) #define botbit(t) (t == 0 ? 64 : __builtin_ctzll(t)) #define gbit(msk, i) ((msk) >> (i) & 1) #define mask(x) ((1LL << (x)) - 1) #define setbits(i, n) \ for(int j = (n), i = botbit(j); j; j ^= 1LL << i, i = botbit(j)) #define rep1(a) for(int i = 0; i < (int)a; i++) #define rep2(i, a) for(int i = 0; i < (int)a; i++) #define rep3(i, a, b) for(int i = a; i < (int)b; i++) #define rep4(i, a, b, c) for(int i = a; i < (int)b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(n) for(ll i = n; i--;) #define rrep2(i, n) for(ll i = n; i--;) #define rrep3(i, a, b) for(ll i = b; i-- > (a);) #define rrep4(i, a, b, c) \ for(ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c) #define rrep(...) \ overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define fore1(i, a) for(auto &&i : a) #define fore2(x, y, a) for(auto &&[x, y] : a) #define fore3(x, y, z, a) for(auto &&[x, y, z] : a) #define fore(...) overload4(__VA_ARGS__, fore3, fore2, fore1)(__VA_ARGS__) #define ryes return yes(); #define rno return no(); #define rerr return err(); istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const pair &p) { os << p.first << "," << p.second; return os; } template ostream &operator<<(ostream &s, set P) { fore(it, P) { s << it << " "; } return s; } template ostream &operator<<(ostream &s, map P) { fore(x, y, P) { s << "<" << x << "->" << y << "> "; } return s; } template ostream &operator<<(ostream &s, multiset P) { fore(it, P) { s << it << " "; } return s; } template ostream &operator<<(ostream &s, unordered_set P) { fore(it, P) { s << it << " "; } return s; } template ostream &operator<<(ostream &s, unordered_map P) { fore(x, y, P) { s << "<" << x << "->" << y << "> "; } return s; } template istream &operator>>(istream &is, vector &v) { for(auto &e : v) is >> e; return is; } template ostream &operator<<(ostream &os, const vector &v) { for(auto &e : v) os << e << ' '; return os; } template ostream &operator<<(ostream &os, const vector> &v) { for(auto &e : v) { for(auto &c : e) os << c << ' '; os << endl; } return os; } template vector &operator++(vector &v) { for(auto &e : v) e++; return v; } template vector operator++(vector &v, signed) { auto res = v; for(auto &e : v) e++; return res; } template vector &operator--(vector &v) { for(auto &e : v) e--; return v; } template vector operator--(vector &v, signed) { auto res = v; for(auto &e : v) e--; return res; } // 十進数からb進数へ template string to_baseB(T x, int b = 10) { string ans; do { int num = x % b; ans = (char)((num <= 9) ? ('0' + num) : ('A' + num - 10)) + ans; x /= b; } while(x != 0); return ans; } // b進数から十進数へ long long to_base10(const string &x, int b = 10) { long long ans = 0, base = 1; for(int i = x.length() - 1; i >= 0; --i) { int num = ('0' <= x[i] && x[i] <= '9') ? (x[i] - '0') : (x[i] - 'A' + 10); ans += base * num; base *= b; } return ans; } ostream &operator<<(ostream &s, const LL &p) { s << to_baseB(p); return s; } // debug methods // usage: debug(x,y); #define CHOOSE(a) CHOOSE2 a #define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x #define debug_1(x1) cout << #x1 << ": " << x1 << endl #define debug_2(x1, x2) \ cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl #define debug_3(x1, x2, x3) \ cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \ << x3 << endl #define debug_4(x1, x2, x3, x4) \ cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \ << x3 << ", " #x4 << ": " << x4 << endl #define debug_5(x1, x2, x3, x4, x5) \ cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \ << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl #ifdef _DEBUG #define debug(...) \ CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \ (__VA_ARGS__) #else #define debug(...) #endif void out() { cout << endl; } template void out(const T &a) { cout << a; cout << endl; } template void out(const T &a, const Ts &...b) { cout << a; (cout << ... << (cout << ' ', b)); cout << endl; } #define rout_1(x1) return out(x1) #define rout_2(x1, x2) return out(x1, x2) #define rout_3(x1, x2, x3) return out(x1, x2, x3) #define rout_4(x1, x2, x3, x4) return out(x1, x2, x3, x4) #define rout_5(x1, x2, x3, x4, x5) return out(x1, x2, x3, x4, x5) #define rout(...) \ CHOOSE((__VA_ARGS__, rout_5, rout_4, rout_3, rout_2, rout_1, ~)) \ (__VA_ARGS__) struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); }; } fast_ios_; struct Binomial { int p; int MAX; vector fac, finv, inv; // テーブルを作る前処理 Binomial(int p_, int n = 1) : p(p_), MAX(1), fac(2), finv(2), inv(2) { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; if(n != 1) build(n); } void build(int new_max) { MAX++; fac.resize(new_max + 1); inv.resize(new_max + 1); finv.resize(new_max + 1); for(; MAX <= new_max; MAX++) { fac[MAX] = fac[MAX - 1] * MAX % p; inv[MAX] = p - inv[p % MAX] * (p / MAX) % p; finv[MAX] = finv[MAX - 1] * inv[MAX] % p; } MAX--; } // nCk long long mod_comb(int n, int k) { if(n < k) return 0; if(n < 0 || k < 0) return 0; if(n > MAX) build(n); return fac[n] * (finv[k] * finv[n - k] % p) % p; } long long operator()(int n, int k) { return mod_comb(n, k); } // nPk long long mod_perm(int n, int k) { if(n < k) return 0; if(n < 0 || k < 0) return 0; if(n > MAX) build(n); return fac[n] * finv[n - k] % p; } // n! long long operator[](int n) { if(n > MAX) build(n); return fac[n]; } // 1/n! long long operator()(int n) { if(n > MAX) build(n); return finv[n]; } }; template struct modpow { long long x, m; int n; vector d; modpow(long long x) : x(x), n(1), d(1, 1) {} T operator[](int i) { while(n <= i) d.push_back(d.back() * x), ++n; return d[i]; } }; modpow two(2), ten(10); struct RandomNumberGenerator { mt19937 mt; RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} long long operator()(long long a, long long b) { // [a, b) uniform_int_distribution dist(a, b - 1); return dist(mt); } long long operator()(long long b) { // [0, b) return (*this)(0, b); } long long operator()() { return (*this)(0, 1LL << 60); } double operator[](double a) { return (double)(*this)(0, 1LL << 60) / (1LL << 60) * a; } double normal_dist(double sigma, double mean = 0) { std::normal_distribution<> dist(mean, sigma); return dist(mt); } } rnd; clock_t start_time = clock(); double now_time() { clock_t end_time = clock(); return (double)(end_time - start_time) / CLOCKS_PER_SEC; } void input_graph(vector> &g, int m = -1, int bidirected = true) { if(m == -1) m = g.size() - 1; for(int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); if(bidirected) g[v].push_back(u); } } vector iota(int n, int s = 0) { vi a(n); iota(a.begin(), a.end(), s); return a; } template void sort(vector &v) { sort(all(v)); } template void rsort(vector &v) { sort(rall(v)); } template void reverse(T &v) { reverse(all(v)); } template auto max(const T &a) { return *max_element(all(a)); } template auto min(const T &a) { return *min_element(all(a)); } long long max(signed x, long long y) { return max((long long)x, y); } long long max(long long x, signed y) { return max(x, (long long)y); } long long min(signed x, long long y) { return min((long long)x, y); } long long min(long long x, signed y) { return min(x, (long long)y); } template bool chmax(T &a, const S &b) { if(a < (T)b) { a = (T)b; return 1; } return 0; } template bool chmin(T &a, const S &b) { if((T)b < a) { a = (T)b; return 1; } return 0; } template vector uniq(vector v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v; } template vector compress(vector v) { vector v2(v.size()); v2 = v; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for(int i = 0; i < (int)v2.size(); i++) { v2[i] = lower_bound(v.begin(), v.end(), v2[i]) - v.begin(); } return v2; } vector inverse(vector &p) { int n = p.size(); vector inv(n); for(int i = 0; i < n; i++) inv[p[i]] = i; return inv; } template vector> idx_pair(vector &a) { int n = a.size(); vector> res(n); for(int i = 0; i < n; i++) res[i] = {a[i], i}; return res; } template vector acc0(vector &v) { vector res(v.size()); if((int)v.size() == 0) return res; res[0] = v[0]; for(int i = 1; i < (int)v.size(); i++) { res[i] = res[i - 1] + v[i]; } return res; } template vector acc1(vector &v) { vector res(v.size() + 1); for(int i = 0; i < (int)v.size(); i++) { res[i + 1] = res[i] + v[i]; } return res; } template vector> acc0(vector> v) { int h = v.size(), w = v[0].size(); for(int i = 0; i < h; i++) { for(int j = 1; j < w; j++) { v[i][j] += v[i][j - 1]; } } for(int i = 1; i < h; i++) { for(int j = 0; j < w; j++) { v[i][j] += v[i - 1][j]; } } return v; } template vector> acc1(vector> &v) { int h = v.size(), w = v[0].size(); vector> res(h + 1, vector(w + 1)); for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { res[i + 1][j + 1] = v[i][j] + res[i + 1][j]; } } for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { res[i + 1][j + 1] += res[i][j + 1]; } } return res; } template void erase1(multiset &st, int x) { auto it = st.find(x); assert(it != st.end()); st.erase(it); } long long exp(long long x, int n) { long long res = 1; while(n > 0) { if(n & 1) res = res * x; x = x * x; n >>= 1; } return res; } int countDigits(long long n) { string tmp = to_string(n); return (int)tmp.size(); } long long sq(long long n) { return n * n; } long long ceil(long long x, long long y) { return (x + y - 1) / y; } long long floor(long long x, long long y) { return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1))); } constexpr long long tri(long long n) { return n * (n + 1) / 2; } // l + ... + r constexpr long long tri(long long l, long long r) { return (l + r) * (r - l + 1) / 2; } int ctoi(const char &c, const char start = '0') { return c - start; } int atoi(const char &c, const char start = 'a') { return c - start; } vector ctoi(string &s, const char start = '0') { vector res; for(auto &c : s) { int x = c - start; if(x < 0 || x >= 10) x = -1; res.push_back(x); } return res; } vector atoi(string &s, const char start = 'a') { vector res; for(auto &c : s) { int x = c - start; if(x < 0 || x >= 26) x = -1; res.push_back(x); } return res; } void yes() { cout << "Yes" << endl; } void no() { cout << "No" << endl; } void yesno(bool x) { if(x) yes(); else no(); } void err() { cout << -1 << endl; } int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; int dy[] = {0, 1, 0, -1, -1, 1, 1, -1}; long long inf = (1 << 30) + (1LL << 60) - 2; double eps = 1e-9; // long long mod = 67280421310721; // using mint = static_modint<1000000009>; // using mint = dynamic_modint<1000000009>; // long long mod = 1000000007; // using mint = modint1000000007; // long long mod = 998244353; // using mint = modint998244353; // typedef vector vm; // typedef vector> vvm; // typedef vector>> vvvm; // Binomial C(mod); // modpow mtwo(2), mten(10); //////////////////////////////////////////////////////////////////////////////////////////// /* https://math314.hateblo.jp/entry/2015/05/07/014908 を参考に int32mod_convolution(vector a, vector b, int mod):O(n log n) */ template T extgcd(T a, T b, T &x, T &y) { for(T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; } template T inv_mod(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; } template class NTT { public: int get_mod() const { return mod; } void _ntt(vector &a, int sign) { const int n = a.size(); assert((n ^ (n & -n)) == 0); // n = 2^k const int g = 3; // g is primitive root of mod int h = (int)pow_mod(g, (mod - 1) / n, mod); // h^n = 1 if(sign == -1) h = (int)inv_mod(h, mod); // h = h^-1 % mod // bit reverse int i = 0; for(int j = 1; j < n - 1; ++j) { for(int k = n >> 1; k > (i ^= k); k >>= 1) ; if(j < i) swap(a[i], a[j]); } for(int m = 1; m < n; m *= 2) { const int m2 = 2 * m; const ll base = pow_mod(h, n / m2, mod); ll w = 1; rep(x, m) { for(int s = x; s < n; s += m2) { ll u = a[s]; ll d = a[s + m] * w % mod; a[s] = u + d; if(a[s] >= mod) a[s] -= mod; a[s + m] = u - d; if(a[s + m] < 0) a[s + m] += mod; } w = w * base % mod; } } for(auto &x : a) if(x < 0) x += mod; } void ntt(vector &input) { _ntt(input, 1); } void intt(vector &input) { _ntt(input, -1); const int n_inv = inv_mod((int)input.size(), mod); for(auto &x : input) x = x * n_inv % mod; } // 畳み込み演算を行う vector convolution(const vector &a, const vector &b) { int ntt_size = 1; while(ntt_size < (int)a.size() + (int)b.size()) ntt_size *= 2; vector _a = a, _b = b; _a.resize(ntt_size); _b.resize(ntt_size); ntt(_a); ntt(_b); rep(i, ntt_size) { (_a[i] *= _b[i]) %= mod; } intt(_a); return _a; } }; ll garner(vector> mr, int mod) { mr.emplace_back(mod, 0); vector coffs(mr.size(), 1); vector constants(mr.size(), 0); rep(i, (int)mr.size() - 1) { // coffs[i] * v + constants[i] == mr[i].second (mod mr[i].first) を解く ll v = (mr[i].second - constants[i]) * inv_mod(coffs[i], mr[i].first) % mr[i].first; if(v < 0) v += mr[i].first; for(int j = i + 1; j < (int)mr.size(); j++) { (constants[j] += coffs[j] * v) %= mr[j].first; (coffs[j] *= mr[i].first) %= mr[j].first; } } return constants[(int)mr.size() - 1]; } typedef NTT<167772161, 3> NTT_1; typedef NTT<469762049, 3> NTT_2; typedef NTT<1224736769, 3> NTT_3; // 任意のmodで畳み込み演算 O(n log n) vector int32mod_convolution(vector a, vector b, int mod) { for(auto &x : a) x %= mod; for(auto &x : b) x %= mod; NTT_1 ntt1; NTT_2 ntt2; NTT_3 ntt3; auto x = ntt1.convolution(a, b); auto y = ntt2.convolution(a, b); auto z = ntt3.convolution(a, b); vector ret(x.size()); vector> mr(3); rep(i, x.size()) { mr[0].first = ntt1.get_mod(), mr[0].second = (int)x[i]; mr[1].first = ntt2.get_mod(), mr[1].second = (int)y[i]; mr[2].first = ntt3.get_mod(), mr[2].second = (int)z[i]; ret[i] = garner(mr, mod); } return ret; } //////////////////////////////////////////////////////////////////////////////////////////// signed main() { int testcase = 1; // cin >> testcase; for(int i = 0; i < testcase; i++) { solve(); } } void solve() { int n; cin >> n; vi a(n + 1); cin >> a; int m; cin >> m; vi b(m + 1); cin >> b; int mod = 258280327; auto ans = int32mod_convolution(a, b, mod); ans.resize(n + m + 1); out(n + m); out(ans); }