Maximum Median Query

Given an array s of length n. For any subarray, define its median as follows: sort the subarray in non-decreasing order (0-indexed) and let the median be the element at index \( \lfloor m/2 \rfloor \), where \( m \) is the length of the subarray.

You are also given an integer Q representing the number of queries. Each query consists of four integers \(a\), \(b\), \(c\), and \(d\) satisfying \(a < b < c < d\). For a query, consider every subarray s[l...r] such that \(l \in [a, b]\) and \(r \in [c, d]\). Your task is to determine the maximum median value among all these subarrays.

Note: The array and indices are 0-indexed.

inputFormat

The first line contains two integers n and Q.

The second line contains n integers representing the array s.

Each of the next Q lines contains four integers \(a\), \(b\), \(c\), and \(d\) (with \(a < b < c < d\)).

outputFormat

For each query, output a single line containing the maximum median among all valid subarrays.

sample

5 2
1 3 2 5 4
0 0 1 4
0 1 2 4

3
4