추월

한 차선짜리 일방통행 도로가 부다페스트 공항에서 호텔 포라스까지 이어져 있다. 도로의 길이는 $L$킬로미터이다.

IOI 2023 행사 기간 동안 $N+1$대의 환승 버스가 이 도로를 달린다. 버스는 0번부터 $N$번까지 번호가 붙어 있다. $i$번 버스($0 \le i < N$)는 행사 시작 후 $T[i]$초에 공항을 출발할 예정이며, 1킬로미터를 $W[i]$초에 주행할 수 있다. $N$번 버스는 예비 버스로, 1킬로미터를 $X$초에 주행할 수 있다. 이 예비 버스가 공항을 출발하는 시각 $Y$는 아직 정해지지 않았다.

도로에서는 원칙적으로 추월할 수 없다. 대신 버스들은 정렬 정류장에서 서로 추월할 수 있다. 정렬 정류장은 $M$개($M > 1$)이며, 0번부터 $M-1$번까지 번호가 붙어 도로 위의 서로 다른 위치에 있다. $j$번 정렬 정류장은 공항에서 $S[j]$킬로미터 떨어져 있다. 정류장은 공항에서 가까운 순서로 놓여 있어, $0 \le j \le M-2$인 모든 $j$에 대해 $S[j] < S[j+1]$이다. 첫 정류장은 공항이고 마지막 정류장은 호텔이다. 즉 $S[0] = 0$, $S[M-1] = L$이다.

버스는 앞서가는 느린 버스를 따라잡지 않는 한 최고 속도로 달린다. 따라잡으면 두 버스는 뭉쳐서 다음 정렬 정류장에 도착할 때까지 느린 버스의 속도로 간다. 그 정류장에서 빠른 버스가 느린 버스를 추월한다.

정확히 말하면, $0 \le i \le N$, $0 \le j < M$인 모든 $i$, $j$에 대해 $t_{i,j}$를 버스 $i$가 정렬 정류장 $j$에 도착하는 시각(초)이라 하자. $0 \le i < N$이면 $t_{i,0} = T[i]$이고, $t_{N,0} = Y$이다. $0 < j < M$인 각 $j$에 대해, 정류장 $j-1$을 떠난 뒤 최고 속도로 달렸을 때 정류장 $j$에 도착하는 예상 도착 시각 $e_{i,j}$를 다음과 같이 정의한다.

$e_{i,j} = t_{i,j-1} + W[i] \cdot (S[j]-S[j-1]) \text{ (} 0 \le i < N \text{인 경우)}$

$e_{N,j} = t_{N,j-1} + X \cdot (S[j]-S[j-1])$

버스 $i$는 $e_{i,j}$와, $t_{k,j-1} < t_{i,j-1}$을 만족하는 모든 버스 $k$($0 \le k \le N$)의 $e_{k,j}$ 중 최댓값에 정류장 $j$에 도착한다.

이 문제에서는 $Q$개의 질의에 답해야 한다. 각 질의는 예비 버스의 출발 시각 $Y$를 준다. 그 때 예비 버스가 호텔에 도착하는 시각을 구하라.

$1 \le L \le 10^9$, $1 \le N \le 1000$, $0 \le i < N$인 모든 $i$에 대해 $0 \le T[i] \le 10^{18}$, $0 \le i < N$인 모든 $i$에 대해 $1 \le W[i] \le 10^9$, $1 \le X \le 10^9$, $2 \le M \le 1000$, $0 = S[0] < S[1] < \cdots < S[M-1] = L$, $1 \le Q \le 10^6$, $0 \le Y \le 10^{18}$.