Problem E
Orz

Joe wants to get a job in Oxbridge Co. which has $n$ ($n \leq 6 \cdot 10^5$) selection contests, in the $i^{th}$ of which the top $a_ i$ ($a_ i \leq 10^9$) competitors get a job. Joe wants to know the probability that he is hired if he participates in the contests $l, l+1, ..., r$, and his rank in each of the contests is uniformly random between $1$ and $x$ ($x \leq 10^9$), with his ranks in different contests being independent. It is guaranteed that for any $i$ we have $a_ i < x$ (meaning that Joe can never get the job with probability $1$).

There are $q \leq 6 \cdot 10^5$ queries, where the values of $a_ i$ are the same over all queries, but the values of $l,r$ and $x$ might change.

Input

In the first line there are two integers $1 \leq n \leq 6 \cdot 10^5$ and $1 \leq q \leq 6 \cdot 10^5$.

In the following line there are $n$ integers, the $i^{th}$ of which is the number $0 \leq a_ i \leq 10^9$.

The following $q$ lines contain one query each, where a query is given by the 3 integers $1 \leq l, r \leq n$ and $x \leq 10^9$.

Output

For each query, output a line containing the answer, i.e the probability that Joe gets hired.

If the absolute error of your output and the answer is within $10^{-6}$, it is considered correct.

3 3
1 2 3
1 1 4
1 2 4
1 3 4

0.250000
0.625000
0.906250