Dengue Affected Areas

Dengue, the talk of the town of Dhaka this year. So many people suffered from dengue fever and a number of people died. In this problem, you are going to process some queries with some given information about the affects of dengue.

There are $n$ most dengue affected areas in Bangladesh. These are numbered from 1 to $n$. The affect value of the $i$-th area is $\text{affect}_i$. Now, you need to process $m$ queries.

A query is defined as L R P Q: You need to print,

• Count of areas numbered from $L$ to $R$ where dengue affect is at least $P$ and at most $Q$.

• Minimum affect value which is present in area $L$ to $R$ and between $P$ to $Q$. If there is no such value, print -1.

• Maximum affect value which is present in area $L$ to $R$ and between $P$ to $Q$. If there is no such value, print -1.

Input

The first line of input will contain two integers $n$ and $m$ ($1 ≤ n, m ≤ 10^5$).

The next line will contain $n$ integers denoting $\text{affect}_1$, $\text{affect}_2$, ..., $\text{affect}_n$ ($1 ≤ \text{affect}_i ≤ 10^9$).

The next $m$ lines will be followed by four integer $L$, $R$, $P$ and $Q$ ($1 ≤ L ≤ R ≤ n$, $1 ≤ P ≤ Q ≤ 10^9$).

Output

For each query, output three integers as defined in the problem statement.

Sample

Input	Output
3 2 1 2 3 1 3 1 3 1 3 4 5	3 1 3 0 -1 -1
In the first query, there are three affect values $[1, 2, 3]$ between $P = 1$ and $Q = 3$ in area $L = 1$ to $R = 3$. So the first integer of the output is 3. Among these, the minimum is 1 and the maximum is 3, so the next two integers of the output is 1 and 2 respectively. In the second query, there is no affect value between $P = 4$ and $Q = 5$ in area $L = 1$ to $R = 3$.