#include #include #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repll(i, n) for (long long i = 0; i < (long long)(n); i++) #define rep2(i, n, m) for (int i = n; i < (int)(m); i++) #define repll2(i, n, m) for (long long i = n; i < (long long)(m); i++) #define all(v) v.begin(),v.end() using ll=long long; using ld=long double; using vi=vector; using vvi=vector; using vvvi=vector; using vl=vector; using vvl=vector; using vvvl=vector; using vld=vector; using vvld=vector; int dx[8]={1,0,-1,0,1,1,-1,-1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; const double PI = acos(-1); //const ll MOD=1e9+7; //const ll MOD=998244353; const ll INF=(1LL<<60); const int INF2=(1<<30); //using mint=modint1000000007; //using mint=modint998244353; using mind=atcoder::modint; // 特殊な剰余と原始根 // (924844033, 5) // (998244353, 3) // (1012924417, 5) // (167772161, 3) // (469762049, 3) // (1224736769, 3) vector prime_list={924844033,998244353,1012924417,167772161,469762049,1224736769}; vector root_list={5,3,5,3,3,3}; unsigned int MOD; unsigned int root; unsigned int add(const unsigned int x, const unsigned int y) { return (x + y < MOD) ? x + y : x + y - MOD; } unsigned int sub(const unsigned int x, const unsigned int y) { return (x >= y) ? (x - y) : (MOD - y + x); } unsigned int mul(const unsigned int x, const unsigned int y) { return (unsigned long long)x * y % MOD; } unsigned int mod_pow(unsigned int x, unsigned int n) { unsigned int res = 1; while(n > 0){ if(n & 1){ res = mul(res, x); } x = mul(x, x); n >>= 1; } return res; } unsigned int inverse(const unsigned int x) { return mod_pow(x, MOD - 2); } void ntt(vector& a, const bool rev = false) { unsigned int i, j, k, l, p, q, r, s; const unsigned int size = a.size(); if(size == 1) return; vector b(size); r = rev ? (MOD - 1 - (MOD - 1) / size) : (MOD - 1) / size; s = mod_pow(root, r); vector kp(size / 2 + 1, 1); for(i = 0; i < size / 2; ++i) kp[i + 1] = mul(kp[i], s); for(i = 1, l = size / 2; i < size; i <<= 1, l >>= 1){ for(j = 0, r = 0; j < l; ++j, r += i){ for(k = 0, s = kp[i * j]; k < i; ++k){ p = a[k + r], q = a[k + r + size / 2]; b[k + 2 * r] = add(p, q); b[k + 2 * r + i] = mul(sub(p, q), s); } } swap(a, b); } if(rev){ s = inverse(size); for(i = 0; i < size; i++){ a[i] = mul(a[i], s); } } } vector convolute(const vector& a, const vector& b) { const int size = (int)a.size() + (int)b.size() - 1; int t = 1; while(t < size){ t <<= 1; } vector A(t, 0), B(t, 0); for(int i = 0; i < (int)a.size(); i++){ A[i] = a[i]; } for(int i = 0; i < (int)b.size(); i++){ B[i] = b[i]; } ntt(A), ntt(B); for (int i = 0; i < t; i++){ A[i] = mul(A[i], B[i]); } ntt(A, true); A.resize(size); return A; } template T mod_add(const T a, const T b, const T mod){ return (a + b) % mod; } template T mod_mul(const T a, const T b, const T mod){ return a * b % mod; } template T mod_inv(T a, T mod){ T u[] = {a, 1, 0}, v[] = {mod, 0, 1}, t; while(*v){ t = *u / *v; swap(u[0] -= t * v[0], v[0]); swap(u[1] -= t * v[1], v[1]); swap(u[2] -= t * v[2], v[2]); } u[1] %= mod; return (u[1] < 0) ? (u[1] + mod) : u[1]; } template T garner(const vector& a, vector p, const T mod){ const unsigned int sz = a.size(); vector kp(sz + 1, 0), rmult(sz + 1, 1); p.push_back(mod); for(unsigned int i = 0; i < sz; ++i){ T x = mod_mul(a[i] - kp[i], mod_inv(rmult[i], p[i]), p[i]); x = (x < 0) ? (x + p[i]) : x; for(unsigned int j = i + 1; j < sz + 1; ++j){ kp[j] = mod_add(kp[j], rmult[j] * x, p[j]); rmult[j] = mod_mul(rmult[j], p[i], p[j]); } } return kp[sz]; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); int n;cin>>n; n++; vl F(n);rep(i,n)cin>>F[i]; int m;cin>>m; m++; vl G(m);rep(i,m)cin>>G[i]; vector> ans(6,vector(n+m)); rep(i,6){ unsigned int p=prime_list[i]; MOD=p; root=root_list[i]; vector Fp(n),Gp(m); rep(i,n)Fp[i]=F[i]%p; rep(i,m)Gp[i]=G[i]%p; auto Hp=convolute(Fp,Gp); rep(j,n+m)ans[i][j]=Hp[j]; } vector res(n+m); vl M={924844033,998244353,1012924417,167772161,469762049,1224736769}; ll deg=0; rep(i,n+m){ vl r; rep(j,6){ r.push_back(ans[j][i]); } res[i]=garner(r,M,ll(258280327)); if(res[i]!=0)deg=i; } cout<