Aby wziąć udział w eliminacjach wojewódzkich, Moorhsum musi przejść przez proces selekcji.

Proces selekcji składa się z $n$ zawodów, w których kwalifikację do etapu wojewódzkiego zdobywają osoby z miejsc od $1$ do $a_i$ w $i$-tych zawodach.

Jako dobry przyjaciel Moorhsum, Goodeat chce obliczyć prawdopodobieństwo, że Moorhsum zakwalifikuje się do etapu wojewódzkiego, jeśli weźmie udział tylko w zawodach od $l$ do $r$, a jego miejsce w każdych zawodach będzie losowane z przedziału $[1, x]$.

Goodeat jednak nie potrafi tego obliczyć, więc prosi Cię o pomoc. Czy możesz mu pomóc?

Wejście

W pierwszej linii znajdują się dwie liczby $n, q$, oznaczające liczbę zawodów oraz liczbę zapytań.

Następnie podano $n$ liczb $a_1 \sim a_n$, oznaczających liczbę miejsc kwalifikujących w każdych zawodach.

W kolejnych $q$ liniach znajdują się trzy liczby $l, r, x$.

Wyjście

Dla każdego zapytania wyprowadź liczbę rzeczywistą oznaczającą prawdopodobieństwo, że Moorhsum zdobędzie kwalifikację, biorąc udział w zawodach od $l$ do $r$, przy założeniu, że jego miejsce w każdych zawodach jest losowane z przedziału $[1, x]$.

Twoja odpowiedź zostanie uznana za poprawną, jeśli jej wartość bezwzględna różnicy od odpowiedzi wzorcowej nie przekracza $10^{-6}$.

Przykład

Przykład 1

Wejście:

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

Wyjście:

0.2500000000
0.6250000000
0.9062500000

Uwagi

Prawdopodobieństwo, że Moorhsum zakwalifikuje się, biorąc udział tylko w pierwszych zawodach, wynosi $1/4$.

Prawdopodobieństwo, że Moorhsum zakwalifikuje się, biorąc udział w pierwszych dwóch zawodach $=$ prawdopodobieństwo kwalifikacji w pierwszych zawodach $+$ prawdopodobieństwo braku kwalifikacji w pierwszych zawodach i kwalifikacji w drugich $= 1/4 + 3/4 \times 1/2 = 5/8$.

Prawdopodobieństwo, że Moorhsum zakwalifikuje się, biorąc udział w pierwszych trzech zawodach $=$ prawdopodobieństwo kwalifikacji w pierwszych dwóch zawodach $+$ prawdopodobieństwo braku kwalifikacji w pierwszych dwóch zawodach i kwalifikacji w trzecich $= 5/8 + 3/8 \times 3/4 = 29/32$.

Przykład 2

Wejście:

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

Wyjście:

0.9806625000
0.6646667215
0.6266061980
0.4417833108
0.0892857143
0.7695473251
0.0063826566

Przykład 3

Patrz załączone pliki.

Podzadania

Dla $20\%$ danych $n, q \leq 500$.

Dla $40\%$ danych $n, q \leq 5000$.

Dodatkowo $30\%$ danych spełnia $n, q \leq 100000$, $l = 1$, $r = n$.

Dla $100\%$ danych $1 \leq n, q \leq 600000$, $1 \leq x \leq 10^9$, $1 \leq a_i \leq 10^9$, $1 \leq l \leq r \leq n$.

Ponieważ Moorhsum najwyraźniej nie ma pewnej kwalifikacji, dane gwarantują, że dla dowolnego $i$, $a_i < x$ (czyli $x > \max(a_1, a_2, ..., a_n)$).