Spare Bus Scheduling

There is a one‐way bike lane road running from Budapest Airport to the Forrás Hotel. The road has a length of \(L\) kilometers. During the IOI 2023 event, \(N+1\) buses are driving on this road. The buses are numbered from \(0\) to \(N\) in order. For each bus \(i\) with \(0 \le i < N\), it is scheduled to depart the airport at time \(T[i]\) (in seconds) and travels at its fastest speed such that driving one kilometer takes \(W[i]\) seconds. Bus \(N\) is the spare bus and drives with a per‐kilometer time of \(X\) seconds. Its departure time \(Y\) from the airport is not fixed.

The road does not generally allow overtaking, except at special locations called scheduling stations. There are \(M\) scheduling stations along the road, numbered from \(0\) to \(M-1\), located at distinct positions along the road. Station \(j\) is located at \(S[j]\) kilometers from the airport. The stations are given in increasing order, i.e. \(S[j] < S[j+1]\) for \(0 \le j .

Each bus drives at its maximum possible speed unless it encounters a slower bus in front. In that case, the faster bus is forced to slow down and follow at the slower bus's speed until they reach the next scheduling station; at the station the fast bus overtakes the slow one. More formally, for every bus \(i\) (\(0 \le i \le N\)) and every station \(j\) (\(0 \le j < M\)) the arrival time at station \(j\) is defined as follows:

• For each \(0 \le i < N\), \(t_{i,0} = T[i]\), and \(t_{N,0} = Y\) for the spare bus.
• For each station \(j\) with \(1 \le j < M\):
  • The expected arrival time for bus \(i\) at station \(j\) is:\\ \(e_{i,j} = t_{i,j-1} + \begin{cases} W[i] \cdot (S[j]-S[j-1]) & \text{if } i < N,\\ X \cdot (S[j]-S[j-1]) & \text{if } i=N. \end{cases}\)
  • The actual arrival time \(t_{i,j}\) is the maximum of its own expected arrival time \(e_{i,j}\) and all expected arrival times \(e_{k,j}\) of buses \(k\) that arrived earlier at station \(j-1\) (i.e. for which \(t_{k,j-1} < t_{i,j-1}\)).

The IOI organizers want to schedule the spare bus (bus \(N\)). Given \(Q\) queries, each specifying a departure time \(Y\) (in seconds) for the spare bus at the airport, your task is to determine the time at which the spare bus arrives at the hotel (i.e. station \(M-1\)).

inputFormat

The input begins with a line containing three integers \(L\), \(N\), and \(M\), where \(L\) is the length of the road in kilometers, \(N\) is the number of non‐spare buses, and \(M\) is the number of scheduling stations (with \(M \ge 2\)).

The second line contains \(N\) integers: \(T[0], T[1], \dots, T[N-1]\) (the departure times for buses \(0\) to \(N-1\)).

The third line contains \(N\) integers: \(W[0], W[1], \dots, W[N-1]\) (the time in seconds that bus \(i\) takes to travel one kilometer).

The fourth line contains one integer \(X\) (the time in seconds per kilometer for the spare bus).

The fifth line contains \(M\) integers: \(S[0], S[1], \dots, S[M-1]\), representing the positions (in kilometers) of the scheduling stations. It is guaranteed that \(S[0] = 0\) and \(S[M-1] = L\), and \(S[j] < S[j+1]\) for \(0 \le j < M-1\).

The next line contains an integer \(Q\), the number of queries. Each of the following \(Q\) lines contains one integer \(Y\) (the departure time in seconds for the spare bus).

outputFormat

For each query, output a single line with one integer: the time (in seconds) at which the spare bus arrives at the hotel (scheduling station \(M-1\)).

sample

10 2 3
0 5
10 5
7
0 5 10
2
3
8

85
85