#line 1 "c.cpp" #include #include #define rep(i,n) for (int i = 0; i < int(n); ++i) #define repp(i,n,m) for (int i = m; i < int(n); ++i) #define reb(i,n) for (int i = int(n)-1; i >= 0; --i) #define all(v) v.begin(),v.end() using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using ld = long double; using P = pair; using PL = pair; using pdd = pair; using pil = pair; using pli = pair; templateistream &operator>>(istream &is,vector &v){for(auto &e:v)is>>e;return is;} templatebool range(T a,T b,T x){return (a<=x&&xbool rrange(T a,T b,T c,T d,T x,T y){return (range(a,c,x)&&range(b,d,y));} template T rev(const T& str_or_vec){T res = str_or_vec; reverse(res.begin(),res.end()); return res; } templatebool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} templatebool chmax(T &a,const T &b){if(avoid uniq(vector &v){sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());} templatevoid print(pair a); templatevoid print(vector v); templatevoid print(vector> v); void print(){ putchar(' '); } void print(bool a){ printf("%d", a); } void print(int a){ printf("%d", a); } void print(long a){ printf("%ld", a); } void print(long long a){ printf("%lld", a); } void print(char a){ printf("%c", a); } void print(char a[]){ printf("%s", a); } void print(const char a[]){ printf("%s", a); } void print(long double a){ printf("%.15Lf", a); } void print(const string& a){ for(auto&& i : a) print(i); } void print(unsigned int a){ printf("%u", a); } void print(unsigned long long a) { printf("%llu", a); } template void print(const T& a){ cout << a; } int out(){ putchar('\n'); return 0; } template int out(const T& t){ print(t); putchar('\n'); return 0; } template int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; } templatevoid print(pair a){print(a.first);print(),print(a.second);} templatevoid print(vector v){for(auto ite=v.begin();ite!=v.end();){print(*ite);if(++ite!=v.end())print();}} templatevoid print(vector> v){for(auto ite=v.begin();ite!=v.end();){print(*ite);if(++ite!=v.end())out();}} void yes(){out("Yes");} void no (){out("No");} void yn (bool t){if(t)yes();else no();} void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout< dx = {0,1,0,-1,1,1,-1,-1}; const vector dy = {1,0,-1,0,1,-1,-1,1}; const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string alp = "abcdefghijklmnopqrstuvwxyz"; const string NUM = "0123456789"; } // namespace noya2 using namespace noya2; using mint = modint998244353; //using mint = modint1000000007; //using mint = modint; void out(mint a){out(a.val());} void out(vector a){vector b(a.size()); rep(i,a.size()) b[i] = a[i].val(); out(b);} void out(vector> a){for (auto v : a) out(v);} istream &operator>>(istream &is,vector &v){for(auto &e:v){ll _x;is>>_x;e=_x;}return is;} #line 2 "FPS_arbitary_mod.hpp" #line 2 "NTT.hpp" #line 4 "NTT.hpp" template struct NTT{ using mint = static_modint; NTT(){init();}; static void FFT(vector &a){ int n = a.size(); int siz = 1; while (siz < n) siz <<= 1; a.resize(siz); fft(a,1); } static void IFFT(vector &a){ int n = a.size(); int siz = 1; while (siz < n) siz <<= 1; mint div = mint(siz).inv(); a.resize(siz); fft(a,-1); for (auto &x : a) x *= div; } static void DFT(vector &a, int inv){fft(a,inv);} static vector multiply(vector a, vector b){ vector na(a.size()), nb(b.size()); for (int i = 0; i < (int)a.size(); i++) na[i] = a[i]; for (int i = 0; i < (int)b.size(); i++) nb[i] = b[i]; vector nc = multiply(na,nb); vector c(nc.size()); for (int i = 0; i < (int)nc.size(); i++) c[i] = nc[i].val(); return c; } static vector multiply(vector a, vector b){ int n = a.size() + b.size() - 1; int siz = 1; while (siz < n) siz <<= 1; a.resize(siz), b.resize(siz); FFT(a), FFT(b); for (int i = 0; i < siz; i++) a[i] *= b[i]; IFFT(a); a.resize(n); return a; } private: static static_modint g; static int limit; static vector>root, inv_root; static constexpr mint primitive_root(const long long &mo){ if (mo == 2) return mint(1); if (mo == 167772161) return mint(3); if (mo == 469762049) return mint(3); if (mo == 754974721) return mint(11); if (mo == 998244353) return mint(3); if (mo == 1224736769)return mint(3); return mint(); // atode kaku } static void init(){ if (!root.empty()) return ; g = primitive_root(m); long long now = m-1; while ((now & 1) == 0) now >>= 1, limit++; root.resize(limit+1,1), inv_root.resize(limit+1,1); root[limit] = g.pow(now), inv_root[limit] /= root[limit]; for(int i = limit-1; i >= 0; i--){ root[i] = root[i+1] * root[i+1]; inv_root[i] = inv_root[i+1] * inv_root[i+1]; } } static int bits_msb(int v){ v = v | (v >> 1); v = v | (v >> 2); v = v | (v >> 4); v = v | (v >> 8); v = v | (v >> 16); return v ^ (v >> 1); } static int pre(int v, int n){ return v ^ (n - bits_msb(v)); } static void fft(vector &a, int inv){ init(); int n = a.size(); if (n == 1) return ; int d = 0; while ((n >> d & 1) == 0) d++; vector idx(n); idx[n-1] = n-1; for (int i = n-2; i >= 0; i--) idx[i] = pre(idx[i+1],n); vector na = a; for (int i = 0; i < n; i++) a[i] = na[idx[i]]; for (int i = 0; i < d; i++){ int width = 1 << (i+1); vector gp(width/2,1); if (inv == 1) for (int j = 0; j < width/2-1; j++) gp[j+1] = gp[j] * root[i+1]; if (inv == -1) for (int j = 0; j < width/2-1; j++) gp[j+1] = gp[j] * inv_root[i+1]; for (int j = 0; j < n; j += width){ for (int k = 0; k < width/2; k++){ mint lhs = a[j+k], rhs = a[j+k+width/2] * gp[k]; a[j+k] = lhs + rhs; a[j+k+width/2] = lhs - rhs; } } } } }; template int NTT::limit=0; template vector>NTT::root=vector>(); template vector>NTT::inv_root=vector>(); template static_modintNTT::g=static_modint(); #line 5 "FPS_arbitary_mod.hpp" namespace noya2{ using namespace std; template struct FormalPowerSeries : vector { using vector::vector; using vector::operator=; using FPS = FormalPowerSeries; void shrink(){while (!(*this).empty() && (*this).back() == mint(0)) (*this).pop_back();} FPS operator+(const mint &r){return FPS(*this) += r;} FPS operator-(const mint &r){return FPS(*this) -= r;} FPS operator*(const mint &r){return FPS(*this) *= r;} FPS operator<<(const int &d){return FPS(*this) <<= d;} FPS operator>>(const int &d){return FPS(*this) >>= d;} FPS operator+(const FPS &r){return FPS(*this) += r;} FPS operator-(const FPS &r){return FPS(*this) -= r;} FPS operator*(const FPS &r){return FPS(*this) *= r;} FPS operator-() const { FPS res(*this); for (mint &x : res) x = -x; return res; } FPS &operator+=(const mint &r){ if ((*this).empty()) (*this).resize(1); (*this)[0] += r; return *this; } FPS &operator-=(const mint &r){ if ((*this).empty()) (*this).resize(1); (*this)[0] -= r; return *this; } FPS &operator*=(const mint &r){ for (mint &x : *this) x *= r; return *this; } FPS &operator<<=(const int &d){ (*this).insert((*this).begin(),d,mint(0)); return *this; } FPS &operator>>=(const int &d){ (*this).erase((*this).begin(),(*this).begin()+d); return *this; } FPS &operator+=(const FPS &r){ const int n = (*this).size(), m = r.size(); (*this).resize(max(n,m)); for (int i = 0; i < m; i++) (*this)[i] += r[i]; return *this; } FPS &operator-=(const FPS &r){ const int n = (*this).size(), m = r.size(); (*this).resize(max(n,m)); for (int i = 0; i < m; i++) (*this)[i] -= r[i]; return *this; } vector arbitrary_mod_convolution(vector ap, vector bp){ const ll MOD = mint::mod(); int sa = ap.size(), sb = bp.size(); vector a(sa), b(sb); for (int i = 0; i < sa; i++) a[i] = ap[i].val(); for (int j = 0; j < sb; j++) b[j] = bp[j].val(); static constexpr ll m1 = 167772161, m2 = 469762049, m3 = 1224736769; static constexpr ll m1_inv_m2 = 104391568, m12_inv_m3 = 721017874; const ll m12_mod = 78812994116517889LL % MOD; auto c1 = NTT::multiply(a,b); auto c2 = NTT::multiply(a,b); auto c3 = NTT::multiply(a,b); vector res(c1.size()); for (int i = 0; i < (int)res.size(); i++){ ll t1 = c1[i]; ll t2 = (c2[i] - c1[i]) * m1_inv_m2 % m2; if (t2 < 0) t2 += m2; ll t3 = (c3[i] - (t1 + t2 * m1) % m3) * m12_inv_m3 % m3; if (t3 < 0) t3 += m3; res[i] = (t1 + t2 * m1 + t3 * m12_mod); } return res; } FPS &operator*=(const FPS &r){ (*this) = arbitrary_mod_convolution((*this),r); //(*this) = NTT::multiply((*this),r); return *this; } mint eval(const mint &x) const { mint res = 0, w = 1; for (auto &e : *this) res += e * w, w *= x; return res; } FPS diff() const { const int n = (*this).size(); FPS res(max(0,n-1)); for (int i = 1; i < n; i++) res[i-1] = (*this)[i] * mint(i); return res; } FPS integral() const { const int n = (*this).size(); vector invs(n+1); invs[1] = mint(1); for (int i = 2; i <= n; i++) invs[i] = -invs[mint::mod()%i] * mint(mint::mod()/i); FPS res(n+1); for (int i = 1; i <= n; i++) res[i] = (*this)[i-1] * invs[i]; return res; } FPS log(int d = -1) const { const int n = (*this).size(); if (d == -1) d = n; FPS res = diff() * mint(d).inv(); res.resize(d-1); return res.integral(); } }; template void fps_out(const FormalPowerSeries &a){ vector _a(a.size()); for (int i = 0; i < (int)a.size(); i++) _a[i] = a[i].val(); out(_a); } } // namespace noya2 #line 78 "c.cpp" const ll mod = 258280327; using fps = FormalPowerSeries>; void solve(){ int n; cin >> n; vector a(n+1); cin >> a; fps f(n+1); rep(i,n+1){ f[i] = a[i]; } int m; cin >> m; vector b(m+1); cin >> b; fps g(m+1); rep(i,m+1){ g[i] = b[i]; } if (n == 0 && a[0] == 0){ out(0); out(0); return ; } if (m == 0 && b[0] == 0){ out(0); out(0); return ; } out(n+m); fps ans = f*g; ans.resize(n+m+1,0); fps_out(f*g); } int main(){ fast_io(); int t = 1; //cin >> t; while(t--) solve(); }