#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #include "utiltime.hpp" using namespace std; typedef long long int ll; typedef vector vi; typedef vector> vvi; typedef pair P; typedef pair Pll; typedef vector vll; typedef vector> vvll; typedef complex cdouble; const int INFL = (int)1e9; const ll INFLL = (ll)1e18; const double INFD = numeric_limits::infinity(); const double PI = 3.14159265358979323846; #define Loop(i, n) for(int i = 0; i < (int)n; i++) #define Loopll(i, n) for(ll i = 0; i < (ll)n; i++) #define Loop1(i, n) for(int i = 1; i <= (int)n; i++) #define Loopll1(i, n) for(ll i = 1; i <= (ll)n; i++) #define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--) #define Looprll(i, n) for(ll i = (ll)n - 1; i >= 0; i--) #define Loopr1(i, n) for(int i = (int)n; i >= 1; i--) #define Looprll1(i, n) for(ll i = (ll)n; i >= 1; i--) #define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++) #define printv(vector) Loop(i, vector.size()) { cout << vector[i] << " "; } cout << endl; #define printmx(matrix) Loop(i, matrix.size()) { Loop(j, matrix[i].size()) { cout << matrix[i][j] << " "; } cout << endl; } #define quickio() ios::sync_with_stdio(false); cin.tie(0); #define bitmanip(m,val) static_cast>(val) ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); } ll floorsqrt(double x) { ll m = (ll)sqrt(x); return m + (m * m <= (ll)(x) ? 0 : -1); } ll ceilsqrt(double x) { ll m = (ll)sqrt(x); return m + ((ll)x <= m * m ? 0 : 1); } ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); } ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); } ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); } /*******************************************************/ namespace Fourier_transform { vector omegas, iomegas; inline int bit_reverse(int x, int digit) { int ret = digit ? x & 1 : 0; Loop(i, digit - 1) { ret <<= 1; x >>= 1; ret |= x & 1; } return ret; } inline void make_omegas(int n) { if (omegas.size() != n) { omegas.resize(n); Loop(i, n) omegas[i] = exp(cdouble({ 0, 2 * PI * i / n })); } } inline void make_iomegas(int n) { if (iomegas.size() != n) { iomegas.resize(n); Loop(i, n) iomegas[i] = exp(cdouble({ 0, -2 * PI * i / n })); } } // a.size() should be 2^digit vector FFT(const vector a) { int n = int(a.size()); int digit = int(rndf(log2(n))); vector ret = a; make_omegas(n); Loop(i, n) { int j = bit_reverse(i, digit); if (j > i) swap(ret[i], ret[j]); } Loop(i, digit) { int j = 0, m = 1 << i, mw = (digit - i - 1); Loop(group_id, n >> (i + 1)) { Loop(k, m) { cdouble x = ret[j] + omegas[k << mw] * ret[j + m]; cdouble y = ret[j] - omegas[k << mw] * ret[j + m]; ret[j] = x; ret[j + m] = y; ++j; } j += m; } } return ret; } // f.size() should be 2^digit vector IFFT(const vector& f) { int n = int(f.size()); int digit = int(rndf(log2(n))); vector ret = f; make_iomegas(n); Loopr(i, digit) { int j = 0, m = 1 << i, mw = (digit - i - 1); Loop(group_id, n >> (i + 1)) { Loop(k, m) { cdouble q = (ret[j] + ret[j + m]) * 0.5; cdouble r = (ret[j] - ret[j + m]) * 0.5 * iomegas[k << mw]; ret[j] = q; ret[j + m] = r; ++j; } j += m; } } Loop(i, n) { int j = bit_reverse(i, digit); if (j > i) swap(ret[i], ret[j]); } return ret; } // a.size() = b.size() should be 2^digit vector mul_convolution(const vector &a, const vector &b) { int n = int(a.size()); vector ret; vector g = FFT(a), h = FFT(b); Loop(i, n) g[i] *= h[i]; ret = IFFT(g); return ret; } int legal_size_of(int n) { int ret = 1 << (int)log2(n); if (ret < n) ret <<= 1; return ret; } } using namespace Fourier_transform; int main() { quickio(); int L, M, N; cin >> L >> M >> N; int n = legal_size_of(N * 2); vector a(n, 0), b(n, 0); Loop(i, L) { int abuf; cin >> abuf; abuf--; a[N - 1 - abuf] = 1; } Loop(i, M) { int bbuf; cin >> bbuf; bbuf--; b[bbuf] = 1; } vector c = mul_convolution(a, b); int q; cin >> q; Loopr(i, q) { cout << rndf(c[i].real()) << endl; } }