#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); } /*******************************************************/ 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; } // a.size() should be 2^digit vector FFT(const vector& a) { int n = int(a.size()); int digit = int(rndf(log2(n))); vector ret(n); vector w(n >> 1); Loop(i, n >> 1) w[i] = exp(cdouble({ 0, 2 * PI * i / n })); Loop(i, n) ret[i] = a[bit_reverse(i, digit)]; 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] + w[k << mw] * ret[j + m]; cdouble y = ret[j] - w[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 a = f; vector w(n >> 1); Loop(i, n >> 1) w[i] = exp(cdouble({ 0, 2 * PI * i / 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 = (a[j] + a[j + m]) / 2.0; cdouble r = (a[j] - a[j + m]) / (w[k << mw] * 2.0); a[j] = q; a[j + m] = r; ++j; } j += m; } } vector ret(n); Loop(i, n) ret[i] = a[bit_reverse(i, digit)]; return ret; } int legal_size_of(int n) { int ret = 1 << (int)log2(n); if (ret < n) ret <<= 1; return ret; } int main() { quickio(); int L, M, N; cin >> L >> M >> N; int n = legal_size_of(N * 2 - 1); vector a(n, 0), b(n, 0); Loop(i, L) { int abuf; cin >> abuf; abuf--; a[abuf] = 1; } Loop(i, M) { int bbuf; cin >> bbuf; bbuf--; if (bbuf == 0) b[0] = 1; else b[n - bbuf] = 1; } vector g = FFT(a); vector h = FFT(b); vector gh(n); Loop(i, gh.size()) { gh[i] = g[i] * h[i]; } vector c = IFFT(gh); int q; cin >> q; Loop(i, q) { cout << rndf(c[i].real()) << endl; } }