为参加省选，Moorhsum必须通过省选选拔。
省选选拔共计 $n$ 场，第 $i$ 场的前 $a_i$ 名获得省选资格。
作为Moorhsum的好朋友，Goodeat想算出如果Moorhsum只参加第 $l$ 场到第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机产生，那么他获得省选资格的概率。
但是Goodeat太莱了，于是他向你求助。你能帮帮他么？
输入格式
第一行两个数 $n$ , $q$ 代表选拔场数和询问次数
接下来n个数 $a_1$ ~ $a_n$ 每场的名额数
随后q行，每行三个数 $l$ $r$ $x$
输出格式
对于每次询问，输出一个小数表示若Moorhsum只参加第 $l$ 场~第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机时获得名额的概率。
你的答案只要与标准答案差的绝对值在 $10^{-6}$ 以内即算正确。
样例一
input
3 3 1 2 3 1 1 4 1 2 4 1 3 4
output
0.2500000000 0.6250000000 0.9062500000
explanation
Moorhsum只参加第一场获得名额的概率为$1/4$Moorhsum参加前两场获得名额的概率 = $第一场获得名额的概率$ + $第一场未获得名额第二场获得的概率$ = $1/4$ + $3/4 * 1/2$ = $5/8$
Moorhsum参加前三场获得名额的概率 = $前两场获得名额的概率$ + $前两场未获得名额第三场获得的概率$ = $5/8$ + $3/8 * 3/4$ = $29/32$
样例二
input
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
0.9806625000 0.6646667215 0.6266061980 0.4417833108 0.0892857143 0.7695473251 0.0063826566
样例三
见样例数据下载限制与约定
对于$20\texttt{%}$的数据 $n, q \leq 500$
对于$40\texttt{%}$的数据 $n, q \leq 5000$
另有$30\texttt{%}$的数据 $n, q \leq 100000$，$l = 1$，$r = n$
对于$100\texttt{%}$的数据 $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$
由于moorhsum显然不能稳进省选，数据保证对于任意$i$，$a[i]$ < $x$ (即 $x$ > $max(a_1, a_2, ..., a_n)$)
时间限制：$3\texttt{s}$
空间限制：$512\texttt{MB}$
