Utkarsh loves finding maximum integers in a given sequence. But this love is not always accompanied with proper knowledge. His teacher once gave him a homework problem and due to his poor knowledge he was not able to solve it. Its 6 in the morning and he has just 2 hours left to solve the problem. Can you help him solve the problem.

He was given an array A consisting of N integers and integers B and M. He had to answer Q queries. Each query is of the form
\(x\space y\) : Print the maximum integer among {\(A_x +B,\space A_{x-y} +2B, \space A_{x-2y} +3B,..., \space A_{x-(M-1)y} +MB \)}

\(INPUT\)
First line contains four integers \(N, Q, B, M\).
Second line contains N integers of array A.
Next Q lines describe Q queries in the form \(x\space y\).

\(OUTPUT\)
Print the answer to each query.

\(CONSTRAINTS\)
\(1 ≤ N,Q,M ≤ 10^5\)
\(-10^9 ≤ A_i\space, B ≤ 10^9\)
\(1 ≤ x,y ≤N\)

Note: Array A is 1-indexed. Do not consider elements in the list if corresponding index in array is non-positive, i.e., do not consider \(A_{x - (i-1)\times y} + iB \) if \( (x - (i-1)\times y) ≤ 0 \)