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 y : Print the maximum integer among {Ax+B, Ax−y+2B, Ax−2y+3B,..., Ax−(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 y.
OUTPUT
Print the answer to each query.
CONSTRAINTS
1≤N,Q,M≤105
−109≤Ai ,B≤109
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 Ax−(i−1)×y+iB if (x−(i−1)×y)≤0
The list of integers for each query: maximum
(Note that in some lists less than three elements are considered because their corresponding array index is non positive)