// Bundled at 2024/08/25 20:08:40 +09:00
// Author: Haar

pub mod main {
    use super::*;
    use haar_lib::{
        algebra::sum::*, algebra::tuple::*, algo::bsearch::*, ds::persistent_segtree::*, get,
        input, utils::fastio::*, utils::join_str::*, utils::transpose::*,
    };
    #[allow(unused_imports)]
    use std::cell::RefCell;
    #[allow(unused_imports)]
    use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
    #[allow(unused_imports)]
    use std::io::Write;
    #[allow(unused_imports)]
    use std::rc::Rc;
    #[derive(Clone, Default)]
    pub struct Problem {}
    impl Problem {
        pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
            let mut io = FastIO::new();
            input!(io >> n: usize, q: usize, mut a: [u64; n]);
            let m = Pair::new(Sum::<u64>::new(), Sum::<usize>::new());
            let mut segs = vec![PersistenSegtree::new(n, m)];
            let mut b = (0..n).map(|i| (a[i], i)).collect::<Vec<_>>();
            b.sort();
            b.reverse();
            for (v, i) in b {
                let s = segs.last().unwrap();
                segs.push(s.assign(i, (v, 1)));
            }
            a.sort();
            for i in 0..q {
                input ! (io >> _t : usize , l : usize , r : usize , x : u64);
                let j = n - lower_bound(&a, &x);
                let (v, c) = segs[j].fold(l - 1..r);
                let ans = v - x * c as u64;
                io.writeln(ans);
            }
            Ok(())
        }
    }
}
fn main() {
    main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod algebra {
    pub mod traits {
        pub trait AlgeStruct {
            type Output;
        }
        pub trait BinaryOp: AlgeStruct {
            fn op(&self, _: Self::Output, _: Self::Output) -> Self::Output;
        }
        pub trait Identity: AlgeStruct {
            fn id(&self) -> Self::Output;
        }
        pub trait Inverse: AlgeStruct {
            fn inv(&self, _: Self::Output) -> Self::Output;
        }
        pub trait Commutative {}
        pub trait Associative {}
        pub trait Idempotence {}
        pub trait Semigroup: BinaryOp + Associative {}
        impl<T: BinaryOp + Associative> Semigroup for T {}
        pub trait Monoid: Semigroup + Identity {}
        impl<T: Semigroup + Identity> Monoid for T {}
        pub trait AbelianMonoid: Monoid + Commutative {}
        impl<T: Monoid + Commutative> AbelianMonoid for T {}
        pub trait Group: Monoid + Inverse {}
        impl<T: Monoid + Inverse> Group for T {}
        pub trait AbelianGroup: Group + Commutative {}
        impl<T: Group + Commutative> AbelianGroup for T {}
        pub trait Exponential<T: Clone>: BinaryOp<Output = T> + Identity {
            fn exp(&self, mut a: Self::Output, mut n: u64) -> Self::Output {
                let mut ret = self.id();
                while n > 0 {
                    if n & 1 == 1 {
                        ret = self.op(ret, a.clone());
                    }
                    a = self.op(a.clone(), a);
                    n >>= 1;
                }
                ret
            }
        }
        impl<T: Clone, A: BinaryOp<Output = T> + Identity> Exponential<T> for A {}
    }
    pub mod sum {
        pub use crate::algebra::traits::*;
        use crate::impl_algebra;
        use std::marker::PhantomData;
        #[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
        pub struct Sum<T>(PhantomData<T>);
        impl<T> Sum<T> {
            pub fn new() -> Self {
                Self(PhantomData)
            }
        }
        impl<T> AlgeStruct for Sum<T> {
            type Output = T;
        }
        impl_algebra!(Sum<i8>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i8| -a, commu: {}, assoc: {});
        impl_algebra!(Sum<i16>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i16| -a, commu: {}, assoc: {});
        impl_algebra!(Sum<i32>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i32| -a, commu: {}, assoc: {});
        impl_algebra!(Sum<i64>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i64| -a, commu: {}, assoc: {});
        impl_algebra!(Sum<i128>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i128| -a, commu: {}, assoc: {});
        impl_algebra!(Sum<isize>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: isize| -a, commu: {}, assoc: {});
        impl_algebra!(Sum<u8>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
        impl_algebra!(Sum<u16>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
        impl_algebra!(Sum<u32>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
        impl_algebra!(Sum<u64>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
        impl_algebra!(Sum<u128>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
        impl_algebra!(Sum<usize>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
        impl_algebra!(Sum<f32>, op: |_, a, b| a + b, id: |_| 0.0, inv: |_, a: f32| -a, commu: {}, assoc: {});
        impl_algebra!(Sum<f64>, op: |_, a, b| a + b, id: |_| 0.0, inv: |_, a: f64| -a, commu: {}, assoc: {});
    }
    pub mod tuple {
        pub use crate::algebra::traits::*;
        #[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
        pub struct Pair<A1, A2>(A1, A2);
        impl<A1, A2> Pair<A1, A2> {
            pub fn new(a1: A1, a2: A2) -> Self {
                Self(a1, a2)
            }
        }
        impl<A1: AlgeStruct, A2: AlgeStruct> AlgeStruct for Pair<A1, A2> {
            type Output = (A1::Output, A2::Output);
        }
        impl<A1: BinaryOp, A2: BinaryOp> BinaryOp for Pair<A1, A2> {
            fn op(&self, a: Self::Output, b: Self::Output) -> Self::Output {
                (self.0.op(a.0, b.0), self.1.op(a.1, b.1))
            }
        }
        impl<A1: Identity, A2: Identity> Identity for Pair<A1, A2> {
            fn id(&self) -> Self::Output {
                (self.0.id(), self.1.id())
            }
        }
        impl<A1: Associative, A2: Associative> Associative for Pair<A1, A2> {}
    }
}
pub mod algo {
    pub mod bsearch {
        macro_rules! bsearch_impl {
    ($t:tt, $a:expr, $value:expr) => {{
        let n = $a.len();
        let mut b = 0;
        let mut len = n;
        while len > 0 {
            let half = len / 2;
            let mid = b + half;
            if &$a[mid] $t $value {
                len -= half + 1;
                b = mid + 1;
            } else {
                len = half;
            }
        }
        b
    }}
}
        #[inline]
        pub fn lower_bound<T: Ord>(a: &[T], value: &T) -> usize {
            bsearch_impl!(<, a, value)
        }
        #[inline]
        pub fn upper_bound<T: Ord>(a: &[T], value: &T) -> usize {
            bsearch_impl!(<=, a, value)
        }
        #[inline]
        pub fn equal_range<T: Ord>(a: &[T], value: &T) -> (usize, usize) {
            (lower_bound(a, value), upper_bound(a, value))
        }
    }
}
pub mod ds {
    pub mod persistent_segtree {
        use crate::algebra::traits::Monoid;
        use std::cell::RefCell;
        use std::ops::Range;
        use std::rc::Rc;
        #[derive(Clone, Debug)]
        struct Node<T> {
            value: T,
            left: Option<Rc<RefCell<Node<T>>>>,
            right: Option<Rc<RefCell<Node<T>>>>,
        }
        impl<T> Node<T> {
            fn new(value: T) -> Self {
                Self {
                    value,
                    left: None,
                    right: None,
                }
            }
        }
        #[derive(Clone, Debug)]
        pub struct PersistenSegtree<M: Monoid> {
            root: Option<Rc<RefCell<Node<M::Output>>>>,
            monoid: M,
            to: usize,
        }
        impl<T: Clone, M: Monoid<Output = T> + Clone> PersistenSegtree<M> {
            pub fn new(n: usize, monoid: M) -> Self {
                let seq = vec![monoid.id(); n];
                Self::from_vec(seq, monoid)
            }

            pub fn from_vec(a: Vec<T>, monoid: M) -> Self {
                let n = a.len();
                let to = if n.is_power_of_two() {
                    n
                } else {
                    n.next_power_of_two()
                };
                let root = Some(Self::__init(0, to, &a, &monoid));
                Self { root, monoid, to }
            }

            fn __init(from: usize, to: usize, seq: &[T], monoid: &M) -> Rc<RefCell<Node<T>>> {
                if to - from == 1 {
                    Rc::new(RefCell::new(Node::new(seq[from].clone())))
                } else {
                    let mid = (from + to) / 2;
                    let mut node = Node::new(monoid.id());
                    let lv = if seq.len() > from {
                        let left = Self::__init(from, mid, seq, monoid);
                        let lv = left.borrow().value.clone();
                        node.left = Some(left);
                        lv
                    } else {
                        monoid.id()
                    };
                    let rv = if seq.len() > mid {
                        let right = Self::__init(mid, to, seq, monoid);
                        let rv = right.borrow().value.clone();
                        node.right = Some(right);
                        rv
                    } else {
                        monoid.id()
                    };
                    node.value = monoid.op(lv, rv);
                    Rc::new(RefCell::new(node))
                }
            }

            fn __set(
                node: Rc<RefCell<Node<T>>>,
                from: usize,
                to: usize,
                pos: usize,
                value: &T,
                monoid: &M,
            ) -> Rc<RefCell<Node<T>>> {
                if to <= pos || pos + 1 <= from {
                    node
                } else if pos <= from && to <= pos + 1 {
                    Rc::new(RefCell::new(Node::new(value.clone())))
                } else {
                    let mid = (from + to) / 2;
                    let lp = node
                        .borrow()
                        .left
                        .clone()
                        .map(|left| Self::__set(left, from, mid, pos, value, monoid));
                    let rp = node
                        .borrow()
                        .right
                        .clone()
                        .map(|right| Self::__set(right, mid, to, pos, value, monoid));
                    let mut s = Node::new(
                        monoid.op(
                            lp.as_ref()
                                .map_or(monoid.id(), |l| l.borrow().value.clone()),
                            rp.as_ref()
                                .map_or(monoid.id(), |r| r.borrow().value.clone()),
                        ),
                    );
                    s.left = lp;
                    s.right = rp;
                    Rc::new(RefCell::new(s))
                }
            }

            pub fn assign(&self, i: usize, value: T) -> Self {
                let new_root = Self::__set(
                    self.root.clone().unwrap(),
                    0,
                    self.to,
                    i,
                    &value,
                    &self.monoid,
                );
                Self {
                    root: Some(new_root),
                    monoid: self.monoid.clone(),
                    to: self.to,
                }
            }

            fn __fold(
                node: Rc<RefCell<Node<T>>>,
                from: usize,
                to: usize,
                l: usize,
                r: usize,
                monoid: &M,
            ) -> T {
                if l <= from && to <= r {
                    node.borrow().value.clone()
                } else if to <= l || r <= from {
                    monoid.id()
                } else {
                    let mid = (from + to) / 2;
                    let lv = node.borrow().left.clone().map_or(monoid.id(), |left| {
                        Self::__fold(left, from, mid, l, r, monoid)
                    });
                    let rv = node.borrow().right.clone().map_or(monoid.id(), |right| {
                        Self::__fold(right, mid, to, l, r, monoid)
                    });
                    monoid.op(lv, rv)
                }
            }

            pub fn fold(&self, Range { start, end }: Range<usize>) -> T {
                Self::__fold(
                    self.root.clone().unwrap(),
                    0,
                    self.to,
                    start,
                    end,
                    &self.monoid,
                )
            }
        }
    }
}
pub mod macros {
    pub mod impl_algebra {
        #[macro_export]
        macro_rules! impl_algebra {
    ($t:ty, op: $f:expr) => {
        impl BinaryOp for $t {
            fn op(&self, a: Self::Output, b: Self::Output) -> Self::Output {
                $f(&self, a, b)
            }
        }
    };
    ($t:ty, id: $f:expr) => {
        impl Identity for $t {
            fn id(&self) -> Self::Output {
                $f(&self)
            }
        }
    };
    ($t:ty, inv: $f:expr) => {
        impl Inverse for $t {
            fn inv(&self, a: Self::Output) -> Self::Output {
                $f(self, a)
            }
        }
    };
    ($t:ty, commu: $f:expr) => {
        impl Commutative for $t {}
    };
    ($t:ty, assoc: $f:expr) => {
        impl Associative for $t {}
    };
    ($t:ty, idem: $f:expr) => {
        impl Idempotence for $t {}
    };
    ($t:ty, $($s:ident: $f:expr),+) => {
        $(
            impl_algebra!($t, $s: $f);
        )+
    }
}
    }
    pub mod io {
        #[macro_export]
        macro_rules! get {
    ( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
        {
            let n = $num;
            (0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
        }
    };
    ( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
        ($(get!($in, $type $(as $to)*)),*)
    };
    ( $in:ident, i8 ) => { $in.read_i64() as i8 };
    ( $in:ident, i16 ) => { $in.read_i64() as i16 };
    ( $in:ident, i32 ) => { $in.read_i64() as i32 };
    ( $in:ident, i64 ) => { $in.read_i64() };
    ( $in:ident, isize ) => { $in.read_i64() as isize };
    ( $in:ident, u8 ) => { $in.read_u64() as u8 };
    ( $in:ident, u16 ) => { $in.read_u64() as u16 };
    ( $in:ident, u32 ) => { $in.read_u64() as u32 };
    ( $in:ident, u64 ) => { $in.read_u64() };
    ( $in:ident, usize ) => { $in.read_u64() as usize };
    ( $in:ident, [char] ) => { $in.read_chars() };
    ( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
        #[macro_export]
        macro_rules! input {
    ( @inner $in:ident, mut $name:ident : $type:tt ) => {
        let mut $name = get!($in, $type);
    };
    ( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
        let mut $name = get!($in, $type as $to);
    };
    ( @inner $in:ident, $name:ident : $type:tt ) => {
        let $name = get!($in, $type);
    };
    ( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
        let $name = get!($in, $type as $to);
    };
    ( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
        $(input!(@inner $in, $($names)* : $type $(as $to)*);)*
    }
}
    }
}
pub mod utils {
    pub mod fastio {
        use std::fmt::Display;
        use std::io::{Read, Write};
        pub struct FastIO {
            in_bytes: Vec<u8>,
            in_cur: usize,
            out_buf: std::io::BufWriter<std::io::Stdout>,
        }
        impl FastIO {
            pub fn new() -> Self {
                let mut s = vec![];
                std::io::stdin().read_to_end(&mut s).unwrap();
                let cout = std::io::stdout();
                Self {
                    in_bytes: s,
                    in_cur: 0,
                    out_buf: std::io::BufWriter::new(cout),
                }
            }

            #[inline]
            pub fn getc(&mut self) -> Option<u8> {
                if self.in_cur < self.in_bytes.len() {
                    self.in_cur += 1;
                    Some(self.in_bytes[self.in_cur])
                } else {
                    None
                }
            }

            #[inline]
            pub fn peek(&self) -> Option<u8> {
                if self.in_cur < self.in_bytes.len() {
                    Some(self.in_bytes[self.in_cur])
                } else {
                    None
                }
            }

            #[inline]
            pub fn skip(&mut self) {
                while self.peek().map_or(false, |c| c.is_ascii_whitespace()) {
                    self.in_cur += 1;
                }
            }

            pub fn read_u64(&mut self) -> u64 {
                self.skip();
                let mut ret: u64 = 0;
                while self.peek().map_or(false, |c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
                    self.in_cur += 1;
                }
                ret
            }

            pub fn read_u32(&mut self) -> u32 {
                self.read_u64() as u32
            }

            pub fn read_usize(&mut self) -> usize {
                self.read_u64() as usize
            }

            pub fn read_i64(&mut self) -> i64 {
                self.skip();
                let mut ret: i64 = 0;
                let minus = if self.peek() == Some(b'-') {
                    self.in_cur += 1;
                    true
                } else {
                    false
                };
                while self.peek().map_or(false, |c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
                    self.in_cur += 1;
                }
                if minus {
                    ret = -ret;
                }
                ret
            }

            pub fn read_i32(&mut self) -> i32 {
                self.read_i64() as i32
            }

            pub fn read_isize(&mut self) -> isize {
                self.read_i64() as isize
            }

            pub fn read_f64(&mut self) -> f64 {
                self.read_chars()
                    .into_iter()
                    .collect::<String>()
                    .parse()
                    .unwrap()
            }

            pub fn read_chars(&mut self) -> Vec<char> {
                self.skip();
                let mut ret = vec![];
                while self.peek().map_or(false, |c| c.is_ascii_graphic()) {
                    ret.push(self.in_bytes[self.in_cur] as char);
                    self.in_cur += 1;
                }
                ret
            }

            pub fn write_rev<T: Display>(&mut self, s: T) {
                let mut s = format!("{}", s);
                let s = unsafe { s.as_bytes_mut() };
                s.reverse();
                self.out_buf.write_all(s).unwrap();
            }

            pub fn write<T: Display>(&mut self, s: T) {
                self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
            }

            pub fn writeln_rev<T: Display>(&mut self, s: T) {
                self.write_rev(s);
                self.out_buf.write_all(&[b'\n']).unwrap();
            }

            pub fn writeln<T: Display>(&mut self, s: T) {
                self.write(s);
                self.out_buf.write_all(&[b'\n']).unwrap();
            }
        }
        impl Drop for FastIO {
            fn drop(&mut self) {
                self.out_buf.flush().unwrap();
            }
        }
    }
    pub mod join_str {
        pub trait JoinStr {
            fn join_str(self, _: &str) -> String;
        }
        impl<T, I> JoinStr for I
        where
            T: ToString,
            I: Iterator<Item = T>,
        {
            fn join_str(self, s: &str) -> String {
                self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
            }
        }
    }
    pub mod transpose {
        pub trait Transpose {
            type Output;
            fn transpose(self) -> Self::Output;
        }
        macro_rules! impl_transpose {
    ($($t:tt),+; $($index:tt),+) => {
        impl<$($t),+> Transpose for Vec<($($t),+)> {
            type Output = ($(Vec<$t>),+);
            fn transpose(self) -> Self::Output {
                let mut ret = ($(Vec::<$t>::new()),+);
                for x in self {
                    $(
                        ret.$index.push(x.$index);
                    )+
                }
                ret
            }
        }
    };
}
        impl_transpose!(T0, T1; 0, 1);
        impl_transpose!(T0, T1, T2; 0, 1, 2);
        impl_transpose!(T0, T1, T2, T3; 0, 1, 2, 3);
        impl_transpose!(T0, T1, T2, T3, T4; 0, 1, 2, 3, 4);
    }
}