Problem: 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.

Input

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 a1, a2, ..., an (0 ≤ ai ≤ 109) are given meaning that person number i initially has ai dollars. 

Each of the next q lines contains three space-separated numbers li, ri, pi (1 ≤ li ≤ ri ≤ n, 0 ≤ p ≤ 1) where li and ri are two integers describing the segment of recommendation and pi 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.

Output

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

Examples

Input

5 2
1 7 2 4 3
1 3 0.500
2 2 0.500


Output

8.000000000


Input

5 2
281 280 279 278 282
1 4 1.000
1 4 0.000


Output

282.000000000


Input

3 5
1 2 3
1 3 0.500
2 2 0.250
1 2 0.800
1 1 0.120
2 2 0.900


Output

4.465000000

Solution (in JAVA):

Solution:
//package codeforces;

        import java.io.*;
        import java.util.*;

public class C {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter writer = new PrintWriter(System.out);
    StringTokenizer stringTokenizer;

    C() throws IOException {
//        reader = new BufferedReader(new FileReader("bridges.in"));
//        writer = new PrintWriter(new FileWriter("bridges.out"));
    }

    String next() throws IOException {
        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            stringTokenizer = new StringTokenizer(reader.readLine());
        }
        return stringTokenizer.nextToken();
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    final int MOD = 1000 * 1000 * 1000 + 7;

    int sum(int a, int b) {
        a += b;
        return a >= MOD ? a - MOD : a;
    }

    int product(int a, int b) {
        return (int) (1l * a * b % MOD);
    }

    int pow(int x, int k) {
        int result = 1;
        while (k > 0) {
            if (k % 2 == 1) {
                result = product(result, x);
            }
            x = product(x, x);
            k /= 2;
        }
        return result;
    }

    int inv(int x) {
        return pow(x, MOD - 2);
    }

    class Q {
        int l, r;
        double p;

        Q(int l, int r, double p) {
            this.l = l;
            this.r = r;
            this.p = p;
        }
    }

    void solve() throws IOException {
        final int n = nextInt();
        final int q = nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = nextInt();
        }
        final Q[] qq = new Q[q];
        for (int i = 0; i < q; i++) {
            qq[i] = new Q(nextInt(), nextInt(), nextDouble());
        }
        double ans = solve(n, q, a, qq);
        writer.println(String.format(Locale.US, "%.10f", ans));
        writer.close();
    }

    void test() {
        final long l = System.currentTimeMillis();
        Q[] q = new Q[5000];
        for (int i = 0; i < 5000; i++) {
            q[i] = new Q(1, 1, 1.);
        }
        System.out.println(solve(1, 5000, new int[]{0, 1000000000}, q));
        System.out.println(0.001 * (System.currentTimeMillis() - l));
    }

    private double solve(final int n, final int q, int[] a, final Q[] qq) {
        Arrays.sort(qq, new Comparator<Q>() {
            @Override
            public int compare(Q o1, Q o2) {
                if(o1.l == o2.l) {
                    return o2.r - o1.r;
                }
                return o1.l - o2.l;
            }
        });
        List<Integer> stack = new ArrayList<>(q);
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            g.add(new ArrayList<Integer>());
        }
        final int[][] graph = new int[q][];
        final List<Integer> roots = new ArrayList<>(q);
        for (int i = 0; i < q; i++) {
            while (!stack.isEmpty() && qq[stack.get(stack.size() - 1)].r < qq[i].l) {
                stack.remove(stack.size() - 1);
            }
            if (stack.isEmpty()) {
                roots.add(i);
            } else {
                g.get(stack.get(stack.size() - 1)).add(i);
            }
            stack.add(i);
        }
        for (int i = 0; i < q; i++) {
            final List<Integer> children = g.get(i);
            graph[i] = new int[children.size()];
            for (int j = 0; j < children.size(); j++) {
                graph[i][j] = children.get(j);
            }
        }
        class SegmentTree {
            int qq = 1;
            int[] a;
            int[] cache = new int[n + 2];
            int[] prevR = new int[n + 2];
            {
                while (qq <= n + 5) {
                    qq *= 2;
                }
                a = new int[2 * qq];
                Arrays.fill(prevR, -1);
            }

            void add(int i, int x) {
                for (i += qq; i > 0; i /= 2) {
                    a[i] = Math.max(a[i], x);
                }
            }

            int max(int l, int r) {
                if(prevR[l] == r) {
                    return cache[l];
                }
                prevR[l] = r;
                int lCopy = l;
                int ret = 0;
                for (l += qq, r += qq; l < r; l /= 2, r /= 2) {
                    if (l % 2 == 1) {
                        ret = Math.max(ret, a[l++]);
                    }
                    if (r % 2 == 1) {
                        ret = Math.max(ret, a[--r]);
                    }
                }
                return cache[lCopy] = ret;
            }
        }
        final SegmentTree segmentTree = new SegmentTree();
        for (int i = 1; i <= n; i++) {
            segmentTree.add(i, a[i]);
        }
        final int max = segmentTree.max(0, n + 1);
        class Utils {
            int[] level = new int[q];

            {
                for (Integer root : roots) {
                    dfs(root);
                }
            }

            void dfs(int u) {
                level[u] = 1;
                for (int v : graph[u]) {
                    dfs(v);
                    level[u] = Math.max(level[u], level[v] + 1);
                }
            }

            double getProb(int s) {
                double p1 = 1.0;
                double p2 = 1.0;
                for (Integer root : roots) {
                    p1 *= getProb(s, root);
                    p2 *= (s == max ? 0 : getProb(s - 1, root));
                }
                return p1 - p2;
            }

            double getProb(int s, int seg) {
                if (segmentTree.max(qq[seg].l, qq[seg].r + 1) > s) {
                    return 0;
                }
                if (segmentTree.max(qq[seg].l, qq[seg].r + 1) + level[seg] <= s) {
                    return 1;
                }
                int l = qq[seg].l;
                boolean foo = false;
                double p1 = qq[seg].p;
                double p2 = 1.0 - p1;
                for (int u : graph[seg]) {
                    if (segmentTree.max(l, qq[u].l) + 1 > s) {
                        foo = true;
                    }
                    l = qq[u].r + 1;
                    if (!foo) {
                        p1 *= getProb(s - 1, u);
                    }
                    p2 *= getProb(s, u);
                }
                if (segmentTree.max(l, qq[seg].r + 1) + 1 > s) {
                    foo = true;
                }
                return p2 + (foo ? 0 : p1);
            }
        }
        class DPUtils extends Utils {
            int low = max - q;
            double[][] dp = new double[q][2 * q + 1];
            {
                for(int k = q - 1; k >= 0; k--) {
                    final int segMax = segmentTree.max(qq[k].l, qq[k].r + 1);
                    for(int i = low; i <= max + q; i++) {
                        if(i > low && dp[k][i - low - 1] == 1.0) {
                            dp[k][i - low] = 1.0;
                            continue;
                        }
                        if (segMax > i) {
                            dp[k][i - low] = 0;
                            continue;
                        }
                        if (segMax + level[k] <= i) {
                            dp[k][i - low] = 1.0;
                            continue;
                        }
                        int l = qq[k].l;
                        boolean foo = false;
                        double p1 = qq[k].p;
                        double p2 = 1.0 - p1;
                        for (int u : graph[k]) {
                            if (segmentTree.max(l, qq[u].l) + 1 > i) {
                                foo = true;
                            }
                            l = qq[u].r + 1;
                            if (!foo) {
//                                p1 *= getProb(i - 1, u);
                                p1 *= i > low ? dp[u][i - low - 1] : 0.0;
                            }
//                            p2 *= getProb(i, u);
                            p2 *= dp[u][i - low];
                        }
                        if (segmentTree.max(l, qq[k].r + 1) + 1 > i) {
                            foo = true;
                        }
                        dp[k][i - low] = p2 + (foo ? 0 : p1);
                    }
                }
            }

            @Override
            double getProb(int s) {
                double p1 = 1.0;
                double p2 = 1.0;
                for (Integer root : roots) {
//                    p1 *= getProb(s, root);
//                    p2 *= (s == max ? 0 : getProb(s - 1, root));
                    p1 *= dp[root][s - low];
                    p2 *= s == max ? 0 : dp[root][s - low - 1];
                }
                return p1 - p2;
            }

            @Override
            double getProb(int s, int seg) {
                throw new RuntimeException();
            }
        }
        Utils utils = new DPUtils();
        double ans = 0;
        for (int i = max; i <= max + q; i++) {
            ans += i * utils.getProb(i);
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        new C().solve();
    }
}