H. Environmental Policy
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Congress has a list of $$$N$$$ policies. Each policy is assigned an environmental impact score of $$$a_i$$$, which represents how much each policy benefits the environment. Help Congress determine the best policies to pass in order to protect the environment.

Congress is given $$$Q$$$ queries in the form of $$$l$$$ $$$r$$$ $$$x$$$ $$$y$$$. Define the "goodness" of a subarray $$$a_i \dots a_j$$$ ($$$1 \le i \le j \le N$$$) to be the average environmental impact score of the elements in that subarray. For each query, determine the maximum "goodness" among all subarrays $$$a_i \dots a_j$$$ whose $$$i$$$ and $$$j$$$ satisfy two constraints:

1. $$$[i, j]$$$ must be fully within the interval $$$[l, r]$$$. That is, $$$l \le i \le j \le r$$$

2. The length of the subarray must be in the range $$$[x, y]$$$. That is, $$$x \le j-i+1 \le y$$$.

For each query, output the floor of the maximum goodness.

Note that due to the large bounds, even fast solutions with an amortized complexity of around $$$O(N^2 log N)$$$ may exceed the time limit.

Input

Line $$$1$$$: Two space separated integers $$$N$$$ ($$$1 \le N \le 10^4$$$) and $$$Q$$$ ($$$1 \le Q \le 10^4$$$).

Line $$$2$$$: $$$N$$$ space separated integers $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) representing the array.

Lines $$$3...Q+2$$$: Four space separated integers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le N$$$), $$$x$$$, and $$$y$$$ ($$$1 \le x \le y \le r - l + 1$$$), corresponding to a query.

Output

Lines $$$1 \dots Q$$$: An integer, representing the floor of the maximum average of a subarray under the constraints of the query.

Example
Input
3 2
-3 2 1
1 3 2 3
1 2 2 2
Output
1
-1