#ifndef Nhoksocqt1
#include "overtaking.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 1003;
ll speed[MAXN], timeLeave[MAXN], nTimeTo[MAXN], timeTo[MAXN], pathLen, busnSpeed;
int staPos[MAXN];
int nArr, mArr;
ll sub1(ll Y) {
if(busnSpeed >= speed[0] || Y <= timeLeave[0])
return Y + pathLen * busnSpeed;
for (int i = 1; i < mArr; ++i) {
if(Y + busnSpeed * staPos[i] <= timeLeave[0] + speed[0] * staPos[i])
return timeLeave[0] + speed[0] * staPos[i] + busnSpeed * (staPos[mArr - 1] - staPos[i]);
}
return Y + pathLen * busnSpeed;
}
ll sub2(ll Y) {
ll res(Y + pathLen * busnSpeed);
for (int i = 0; i < nArr; ++i) {
if(timeLeave[i] < Y)
res = max(res, timeLeave[i] + speed[i] * pathLen);
}
return res;
}
ll arrival_time(ll Y) {
if(nArr == 1)
return sub1(Y);
if(mArr == 2)
return sub2(Y);
for (int i = 0; i < nArr; ++i)
timeTo[i] = timeLeave[i];
ll res(Y);
for (int i = 1; i < mArr; ++i) {
ll timeNow = res + (staPos[i] - staPos[i - 1]) * busnSpeed;
for (int j = 0; j < nArr; ++j) {
if(timeTo[j] < res)
timeNow = max(timeNow, timeTo[j] + (staPos[i] - staPos[i - 1]) * speed[j]);
nTimeTo[j] = timeTo[j] + (staPos[i] - staPos[i - 1]) * speed[j];
for (int k = 0; k < nArr; ++k) {
if(timeTo[k] < timeTo[j])
nTimeTo[j] = max(nTimeTo[j], timeTo[k] + (staPos[i] - staPos[i - 1]) * speed[k]);
}
}
for (int j = 0; j < nArr; ++j)
timeTo[j] = nTimeTo[j];
res = timeNow;
}
return res;
}
void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S) {
pathLen = _L, nArr = _N, mArr = _M, busnSpeed = _X;
for (int i = 0; i < nArr; ++i)
speed[i] = _W[i];
for (int i = 0; i < nArr; ++i)
timeLeave[i] = _T[i];
for (int i = 0; i < mArr; ++i)
staPos[i] = _S[i];
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "overtaking"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<ll> _T;
vector<int> _W, _S;
int _L, _N, _M, _X;
cin >> _L >> _N;
_T.resize(_N);
for (int i = 0; i < _N; ++i)
cin >> _T[i];
_W.resize(_N);
for (int i = 0; i < _N; ++i)
cin >> _W[i];
cin >> _X >> _M;
_S.resize(_M);
for (int i = 0; i < _M; ++i)
cin >> _S[i];
init(_L, _N, _T, _W, _X, _M, _S);
int _Q;
cin >> _Q;
for (int t = 0; t < _Q; ++t) {
ll _Y;
cin >> _Y;
cout << "ASK " << _Y << ": ";
cout << arrival_time(_Y) << '\n';
}
return 0;
}
#endif // Nhoksocqt1
