#include #include #include #include #include #include using namespace std; using ll = long long int; using Complex = complex; vector dft(vector A, int N, int sgn = 1) { if(N == 1) return A; vector F(N / 2), G(N / 2); for(int i=0; i inv_dft(vector A, int N) { A = dft(A, N, -1); for(int i=0; i multiply(vector A, vector B) { int sz = A.size() + B.size() + 1; int N = 1; while(N < sz) N *= 2; A.resize(N), B.resize(N); A = dft(A, N), B = dft(B, N); vector F(N); for(int i=0; i> L >> M >> N; vector A(N), B(N); vector X(N), Y(N); for(int i=0; i> val; val--; A[val]++; } for(int i=0; i> val; B[N - val]++; } for(int i=0; i ans = multiply(X, Y); int Q; cin >> Q; for(int i=0; i