SOLVE
LATER
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 $$
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)