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:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.util.Deque;
import java.util.OptionalInt;
import java.util.ArrayList;
import java.math.BigDecimal;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.util.Collection;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CHelpingPeople solver = new CHelpingPeople();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CHelpingPeople {
        int low;
        int high;

        public double[] dfs(Node root) {
            double[] dp = new double[high - low + 1];
            int v = root.init - low;
            v = Math.max(v, 0);
            for (int i = v; i < dp.length; i++) {
                dp[i] = 1;
            }
            for (Node node : root.adj) {
                double[] prob = dfs(node);
                for (int i = 0; i < dp.length; i++) {
                    dp[i] *= prob[i];
                }
            }
            for (int i = dp.length - 1; i >= 1; i--) {
                dp[i] = dp[i] * (1 - root.prob) + dp[i - 1] * root.prob;
            }
            return dp;
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int q = in.ri();
            int[] a = in.ri(n);
            int max = Arrays.stream(a).max().orElse(-1);
            low = max - q;
            high = max + q;
            Deque<Node> dq = new ArrayDeque<>(q);
            Node[] nodes = new Node[q + 1];
            for (int i = 0; i < q; i++) {
                nodes[i] = new Node();
                nodes[i].l = in.ri() - 1;
                nodes[i].r = in.ri() - 1;
                nodes[i].prob = in.rd();
            }
            Node whole = new Node();
            whole.l = 0;
            whole.r = n - 1;
            whole.prob = 0;
            nodes[q] = whole;
            Arrays.sort(nodes, Comparator.<Node>comparingInt(x -> x.l).thenComparingInt(x -> -x.r));

            for (Node node : nodes) {
                while (!dq.isEmpty() && dq.peekLast().r < node.l) {
                    dq.removeLast();
                }
                if (!dq.isEmpty() && dq.peekLast().r >= node.r) {
                    dq.peekLast().adj.add(node);
                }
                dq.addLast(node);
            }
            for (Node node : nodes) {
                node.init = -(int) 1e9;
                int last = node.l;
                for (Node child : node.adj) {
                    for (int i = last; i < child.l; i++) {
                        node.init = Math.max(node.init, a[i]);
                    }
                    last = child.r + 1;
                }
                for (int i = last; i <= node.r; i++) {
                    node.init = Math.max(node.init, a[i]);
                }
            }

            double[] prob = dfs(nodes[0]);
            double exp = 0;
            for (int i = 1; i < prob.length; i++) {
                exp += (i + low) * (prob[i] - prob[i - 1]);
            }
            out.println(exp);
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(int[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readInt();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int[] ri(int n) {
            int[] ans = new int[n];
            populate(ans);
            return ans;
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public double rd() {
            return readDouble();
        }

        public double readDouble() {
            boolean sign = true;
            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+';
                next = read();
            }

            double val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 + next - '0';
                next = read();
            }
            if (next != '.') {
                return sign ? val : -val;
            }
            next = read();
            double radix = 1;
            while (next >= '0' && next <= '9') {
                val = val * 10 + next - '0';
                radix = radix * 10;
                next = read();
            }
            double result = val / radix;
            return sign ? result : -result;
        }

    }

    static class Node {
        double prob;
        int init;
        int l;
        int r;
        List<Node> adj = new ArrayList<>();

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(double c) {
            cache.append(new BigDecimal(c).toPlainString());
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(double c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}