IOI Tower Climb

IOI Tower is an extremely tall tower with a staircase consisting of \(10^{100}\) steps numbered from \(0\) upward. JOI is at step \(0\) and wishes to climb the tower. He has two moves:

• Move up one step. This costs \(A\) seconds.
• Jump exactly \(D\) steps upward (i.e. from step \(x\) to step \(x+D\)). This costs \(B\) seconds.

However, some portions of the staircase are under construction. There are \(N\) construction intervals. The \(i\)-th construction covers all steps from \(L_i\) to \(R_i\) (inclusive) where JOI cannot step. Note that the jump move allows JOI to skip over intermediate steps even if they are under construction, but the landing step must be safe.

Moreover, the tower has \(Q\) rooms. For each \(j\) (\(1 \le j \le Q\)), room \(j\) can be entered from step \(X_j\). For each room, determine whether JOI can reach the room and if so, compute the minimum time required.

Note: JOI is not allowed to move downward.

inputFormat

The input is given in the following format:

A B D N Q
L1 R1
L2 R2
... (N lines in total)
X1
X2
... (Q lines in total)

All numbers are integers. It is guaranteed that the staircase has \(10^{100}\) levels, but all positions that appear in the input (i.e. in obstacles and queries) are within a reasonable range.

outputFormat

Print \(Q\) lines. For each \(j\) (\(1 \le j \le Q\)), if JOI can reach step \(X_j\), output the minimum time required; otherwise, output \(-1\).

sample

1 2 2 1 3
2 3
1
2
4

1
-1
-1