module Main;

import CPLib.DSegtree::fold;
import CPLib.IO;
import CPLib.Monoid;
import CPLib.Segtree;

main : IO () = (
    let n = *read_i;
    let q = *read_i;
    let as = *read_is(n);
    let as_sorted = as.to_iter.enumerate.to_array.sort_by(|(a, b)| a.@1 > b.@1);
    let tree : Segtree (Sum I64) = Segtree::create(n);
    let cnt : Segtree (Sum I64) = Segtree::create(n);
    let qs = *range(0, q).fold_m([], |i, qs|
        let _t = *read_i;
        let l = *read_i - 1;
        let r = *read_i;
        let x = *read_i;
        qs.push_back((i, l, r, x)).pure
    );
    let qs = qs.sort_by(|((_, _, _, x), (_, _, _, y))| x > y);
    let ans = fill(q, 0);
    let (ans, _, _, _) = range(0, q).fold((ans, 0, tree, cnt), |q, (ans, as_sorted_i, tree, cnt)|
        let (i, l, r, x) = qs.@(q);
        let as_sorted_ib = as_sorted_i;
        let as_sorted_i = loop(as_sorted_i, |as_sorted_i|
            if as_sorted_i >= n { n.break };
            let (_, a) = as_sorted.@(as_sorted_i);
            if a < x { as_sorted_i.break };
            continue $ as_sorted_i + 1
        );
        let (tree, cnt) = range(as_sorted_ib, as_sorted_i).fold((tree, cnt), |as_sorted_i, (tree, cnt)|
            let (i, a) = as_sorted.@(as_sorted_i);
            let tree = tree.set(i, Sum { v: a });
            let cnt = cnt.set(i, Sum { v: 1 });
            (tree, cnt)
        );
        let sum = tree.fold(l, r).@v // x 以上のものの和
            - x * cnt.fold(l, r).@v; // x * (x以上のものの個数)
        let ans = ans[i].iset(sum);
        (ans, as_sorted_i, tree, cnt)
    );
    "{}".printfln((ans.to_iter.joined_with("\n"),));;
    pure()
);