Для участия в региональном отборе Moorhsum должен пройти квалификацию.
Всего проводится $n$ отборочных этапов, и на $i$-м этапе право на прохождение получают участники, занявшие места с $1$ по $a_i$.
Будучи хорошим другом Moorhsum, Goodeat хочет вычислить вероятность того, что Moorhsum получит квалификацию, если он примет участие только в этапах с $l$ по $r$, а его место в каждом этапе будет случайным образом выбрано из диапазона $[1, x]$.
Однако Goodeat не справляется с этой задачей, поэтому он просит вас о помощи. Можете ли вы ему помочь?
Входные данные
Первая строка содержит два числа $n$ и $q$ — количество отборочных этапов и количество запросов соответственно.
Далее следуют $n$ чисел $a_1 \sim a_n$, обозначающих количество квалификационных мест на каждом этапе.
Затем следуют $q$ строк, каждая из которых содержит три числа $l, r, x$.
Выходные данные
Для каждого запроса выведите десятичную дробь, представляющую вероятность того, что Moorhsum получит квалификацию, если он участвует в этапах с $l$ по $r$, а его место в каждом этапе случайно выбирается из диапазона $[1, x]$.
Ваш ответ считается верным, если его абсолютная погрешность по сравнению с правильным ответом не превышает $10^{-6}$.
Примеры
Пример 1
Входные данные
3 3 1 2 3 1 1 4 1 2 4 1 3 4
Выходные данные
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
Выходные данные
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)$).