CF494C.Helping People

Malek is a rich man. He also is very generous. That's why he decided to split his money between poor people. A charity institute knows n poor people numbered from 1 to n. The institute gave Malek q recommendations. A recommendation is a segment of people like [l, r] which means the institute recommended that Malek gives one dollar to every person whose number is in this segment.

However this charity has very odd rules about the recommendations. Because of those rules the recommendations are given in such a way that for every two recommendation [a, b] and [c, d] one of the following conditions holds:

• The two segments are completely disjoint. More formally either a ≤ b < c ≤ d or c ≤ d < a ≤ b
• One of the two segments are inside another. More formally either a ≤ c ≤ d ≤ b or c ≤ a ≤ b ≤ d.

The goodness of a charity is the value of maximum money a person has after Malek finishes giving his money. The institute knows for each recommendation what is the probability that Malek will accept it. They want to know the expected value of goodness of this charity. So they asked you for help.

You have been given the list of recommendations and for each recommendation the probability of it being accepted by Malek. You have also been given how much money each person initially has. You must find the expected value of goodness.

马莱克是一位富有的人，同时也非常慷慨。因此，他决定将自己的钱分给穷人。一家慈善机构掌握了编号为 $1$ 到 $n$ 的 $n$ 位穷人信息。该机构向马莱克提出了 $q$ 条建议。每条建议是一个人群区间 $[l,\,r]$，表示该机构建议马莱克向编号落在该区间内的每个人各赠送一美元。

然而，这家慈善机构关于建议的规则十分特殊。正因如此，所有建议均满足如下性质：对任意两条建议 $[a,\,b]$ 和 $[c,\,d]$，以下条件之一必然成立：

• 这两个区间完全不相交。更准确地说，要么满足 $a \le b < c \le d$，要么满足 $c \le d < a \le b$；
• 其中一个区间完全包含于另一个区间内。更准确地说，要么满足 $a \le c \le d \le b$，要么满足 $c \le a \le b \le d$。

该慈善机构的“优良度”定义为：在马莱克完成所有赠款后，所有人中所拥有的钱数的最大值。该机构已知每条建议被马莱克接受的概率，现希望计算该慈善机构优良度的期望值。因此，他们向你寻求帮助。

你已获得所有建议列表，以及每条建议被马莱克接受的概率。你还已知每位穷人初始拥有的钱数。请计算优良度的期望值。

In the first line two space-separated integers n, q (1 ≤ n ≤ 105, 1 ≤ q ≤ 5000) are given.

In the second line n space-separated integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 109) are given meaning that person number i initially has a__i dollars.

Each of the next q lines contains three space-separated numbers l__i, r__i, p__i (1 ≤ l__i ≤ r__i ≤ n, 0 ≤ p ≤ 1) where l__i and r__i are two integers describing the segment of recommendation and p__i is a real number given with exactly three digits after decimal point which is equal to probability of Malek accepting this recommendation.

Note that a segment may appear several times in recommendations.

第一行给出两个用空格分隔的整数 $n$ 和 $q$（$1 \leq n \leq 10^5$，$1 \leq q \leq 5000$）。

第二行给出 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 10^9$），表示编号为 $i$ 的人最初拥有 $a_i$ 美元。

接下来的 $q$ 行中，每行包含三个用空格分隔的数 $l_i, r_i, p_i$（$1 \leq l_i \leq r_i \leq n$，$0 \leq p \leq 1$），其中 $l_i$ 和 $r_i$ 是描述推荐区间的两个整数，$p_i$ 是一个保留三位小数的实数，表示 Malek 接受该推荐的概率。

注意：同一个区间可能在多个推荐中多次出现。

Output the sought value. Your answer will be considered correct if its absolute or relative error is less than 10 - 6.

输出所求的值。若您的答案的绝对误差或相对误差小于 $10^{-6}$，则视为正确。