To participate in the provincial selection, Moorhsum must pass the selection trials.

There are $n$ selection trials in total, and the top $a_i$ participants in the $i$-th trial qualify for the provincial selection.

As a good friend of Moorhsum, Goodeat wants to calculate the probability that Moorhsum qualifies if he only participates in trials from $l$ to $r$, and his rank in each trial is generated randomly in the range $[1, x]$.

However, Goodeat is not skilled enough, so he asks for your help. Can you help him?

Input

The first line contains two integers $n$ and $q$, representing the number of trials and the number of queries.

The next line contains $n$ integers $a_1 \sim a_n$, representing the number of qualifying spots for each trial.

Following this are $q$ lines, each containing three integers $l, r, x$.

Output

For each query, output a decimal representing the probability that Moorhsum qualifies if he participates only in trials $l$ through $r$, and his rank in each trial is randomly generated in $[1, x]$.

Your answer will be considered correct if the absolute difference between your answer and the standard answer is within $10^{-6}$.

Examples

Input 1

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

Output 1

0.2500000000
0.6250000000
0.9062500000

Note 1

The probability that Moorhsum qualifies by participating only in the first trial is $1/4$.

The probability that Moorhsum qualifies by participating in the first two trials $=$ (probability of qualifying in the first trial) $+$ (probability of not qualifying in the first trial and qualifying in the second trial) $= 1/4 + 3/4 \times 1/2 = 5/8$.

The probability that Moorhsum qualifies by participating in the first three trials $=$ (probability of qualifying in the first two trials) $+$ (probability of not qualifying in the first two trials and qualifying in the third trial) $= 5/8 + 3/8 \times 3/4 = 29/32$.

Input 2

10 7
3 7 19 6 8 7 2 3 5 4
1 4 20
4 6 23
5 7 21
4 10 63
9 9 56
3 4 27
1 10 10000

Output 2

0.9806625000
0.6646667215
0.6266061980
0.4417833108
0.0892857143
0.7695473251
0.0063826566

Input 3

See the provided files.

Subtasks

For $20\%$ of the data, $n, q \leq 500$.

For $40\%$ of the data, $n, q \leq 5000$.

An additional $30\%$ of the data satisfies $n, q \leq 100000$, $l = 1$, and $r = n$.

For $100\%$ of the data, $1 \leq n, q \leq 600000$, $1 \leq x \leq 10^9$, $1 \leq a_i \leq 10^9$, and $1 \leq l \leq r \leq n$.

Since Moorhsum is clearly not guaranteed to qualify, the data guarantees that for any $i$, $a_i < x$ (i.e., $x > \max(a_1, a_2, \dots, a_n)$).