题目描述

为参加省选，Moorhsum 必须通过省选选拔。

省选选拔共计 $n$ 场，第 $i$ 场的前 $a_i$ 名获得省选资格。

作为 Moorhsum 的好朋友，Goodeat 想算出如果 Moorhsum 只参加第 $l$ 场到第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机产生，那么他获得省选资格的概率。

但是 Goodeat 太莱了，于是他向你求助。你能帮帮他么？

输入格式

第一行两个数 $n, q$ 代表选拔场数和询问次数

接下来 $n$ 个数 $a_1\sim a_n$ 每场的名额数

随后 $q$ 行，每行三个数 $l, r, x$

输出格式

对于每次询问，输出一个小数表示若 Moorhsum 只参加第 $l$ 场 $\sim$ 第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机时获得名额的概率。

你的答案只要与标准答案差的绝对值在 $10^{-6}$ 以内即算正确。

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

0.2500000000
0.6250000000
0.9062500000

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

0.9806625000
0.6646667215
0.6266061980
0.4417833108
0.0892857143
0.7695473251
0.0063826566

样例 3

见 [ex_gjx3.in](file:ex_gjx3.in) 与 [ex_gjx3.out](file:ex_gjx3.out)

数据范围与提示

对于 $20\%$ 的数据 $n, q \leq 500$

对于 $40\%$ 的数据 $n, q \leq 5000$

另有 $30\%$ 的数据 $n, q \leq 100000$，$l = 1$，$r = n$

对于 $100\%$ 的数据 $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)$）