為了參加省選，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}$ 以內即算正確。

範例

範例輸入 1

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

範例輸出 1

0.2500000000
0.6250000000
0.9062500000

說明 1

Moorhsum 只參加第一場獲得名額的機率為 $1/4$。

Moorhsum 參加前兩場獲得名額的機率 $=$ 第一場獲得名額的機率 $+$ 第一場未獲得名額第二場獲得的機率 $= 1/4 + 3/4 \times 1/2 = 5/8$。

Moorhsum 參加前三場獲得名額的機率 $=$ 前兩場獲得名額的機率 $+$ 前兩場未獲得名額第三場獲得的機率 $= 5/8 + 3/8 \times 3/4 = 29/32$。

範例輸入 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

範例輸出 2

0.9806625000
0.6646667215
0.6266061980
0.4417833108
0.0892857143
0.7695473251
0.0063826566

範例 3

見下發文件。

子任務

對於 $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)$）。