為了參加省選，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)$）。