#include<bits/stdc++.h>
using namespace std;

#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define aint(x) (x).begin(),(x).end()

#define int long long
#define fi first
#define se second

struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;


	//乱数系
random_device rnd; 
mt19937 mt(rnd());
const long long MT_MAX=1e18;
uniform_int_distribution<long long> rd(0,MT_MAX);
double randd(){
    return 1.0*rd(mt)/MT_MAX;
}
long long randint(long long a,long long b){
    // [a,b]の乱数を生成
    return a+rd(mt)%(b-a+1);
}


template<class T> T SortedMultiList_default_op(T a,T b){return max(a,b);}
template<class T> T SortedMultiList_default_e(){return 0;}

template<class T,T(*op)(T,T)/*=SortedMultiList_default_op<T>*/,T(*e)()/*=SortedMultiList_default_e<T>*/>

class SortedMultiList{
    struct Node{
        T key,acc;
        int priority,cnt;
        Node *l,*r;
        Node(T key,int priority):key(key),acc(key),priority(priority),cnt(1),l(nullptr),r(nullptr){}
    }*root=nullptr;
    using Tree=Node*;
    
    int cnt(Tree t){
        return t?t->cnt:0;
    }
    
    T acc(Tree t){
        return t?t->acc:e();
    }

    void update(Tree &t){
        if(t){
            t->cnt=1+cnt(t->l)+cnt(t->r);
            t->acc=op(op(acc(t->l),t->key),acc(t->r));
        }
    }

    void split(Tree t,T key,Tree &l,Tree &r){
        if(!t){
            l=r=nullptr;
        }else if(key<t->key){
            split(t->l,key,l,t->l),r=t;
        }else{
            split(t->r,key,t->r,r),l=t;
        }
        update(t);
    }

    void split_by_index(Tree t,int idx,Tree &l,Tree &r){
        if(!t){
            l=r=nullptr;
        }else if(cnt(t->l)>=idx){
            split_by_index(t->l,idx,l,t->l),r=t;
        }else{
            split_by_index(t->r,idx-cnt(t->l)-1,t->r,r),l=t;
        }
        update(t);
    }

    void merge(Tree &t,Tree l,Tree r){
        if(!l||!r){
            t=l?l:r;
        }else if(l->priority>r->priority){
            merge(l->r,l->r,r),t=l;
        }else{
            merge(r->l,l,r->l),t=r;
        }
        update(t);
    }

    void insert(Tree &t,Tree item){
        if(!t){
            t=item;
        }else if(item->priority>t->priority){
            split(t,item->key,item->l,item->r),t=item;
            update(t);
        }else{
            insert(item->key<t->key?t->l:t->r,item);
            update(t);
        }
    }

    void erase(Tree &t,T key){
        if(!t)return;
        if(t->key==key){
            merge(t,t->l,t->r);
            update(t);
        }else{
            erase(key<t->key?t->l:t->r,key);
            update(t);
        }
    }

    bool find(Tree &t,T key){
        if(!t){
            return false;
        }else if(t->key==key){
            return true;
        }else{
            return find(key<t->key?t->l:t->r,key);
        }
    }

    T index(Tree &t,int idx){
        int siz=(t->l?t->l->cnt:0);
        if(idx==siz){
            return t->key;
        }else if(idx<siz){
            return index(t->l,idx);
        }else{
            return index(t->r,idx-siz-1);
        }
    }

    int lower_bound(Tree &t,T key){
        if(!t)return 0;
        int siz=(t->l?t->l->cnt:0);
        if(t->key>=key){
            return lower_bound(t->l,key);
        }else{
            return siz+1+lower_bound(t->r,key);
        }
    }

    int upper_bound(Tree &t,T key){
        if(!t)return 0;
        int siz=(t->l?t->l->cnt:0);
        if(t->key>key){
            return upper_bound(t->l,key);
        }else{
            return siz+1+upper_bound(t->r,key);
        }
    }

    T prod(Tree t,int l,int r){
        Tree t1,t2,t3;
        split_by_index(t,l,t1,t2);
        split_by_index(t2,r-l,t2,t3);
        T res=acc(t2);
        merge(t2,t2,t3);
        merge(t,t1,t2);
        return res;
    }

    template<class F>
    int max_right(Tree t,const F &f,T product){
        if(!f(product))return 0;
        if(f(op(product,acc(t))))return cnt(t);
        int m=max_right(t->l,f,product);
        if(m<cnt(t->l))return m;
        product=op(product,acc(t->l));
        if(!f(op(product,t->key)))return cnt(t->l);
        product=op(product,t->key);
        return cnt(t->l)+1+max_right(t->r,f,product);
    }

    template<class F>
    int min_left(Tree t,const F &f,T product){
        if(!f(product))return cnt(t);
        if(f(op(product,acc(t))))return 0;
        int m=min_left(t->r,f,product);
        if(0<m)return cnt(t->l)+1+m;
        product=op(product,acc(t->r));
        if(!f(op(product,t->key)))return cnt(t->l)+1;
        product=op(product,t->key);
        return min_left(t->l,f,product);
    }

    void to_vector(Tree t,vector<T> &vec){
        if(!t)return;
        to_vector(t->l,vec);
        vec.push_back(t->key);
        to_vector(t->r,vec);
    };

    void dump(Tree t){
        if(!t)return;
        if(t->l){
            dump(t->l);cout<<" ";
        }
        cout<<t->key;
        if(t->r){
            cout<<" ";dump(t->r);
        }
    };

    public:

    void insert(T key){
        insert(root,new Node(key,randint(0,1LL<<63)));
    }

    void erase(T key){
        erase(root,key);
    }

    bool find(T key){
        return find(root,key);
    }

    T index(int idx){
        return index(root,idx);
    }

    T operator[](int idx){
        return index(root,idx);
    }

    int lower_bound(T key){
        return lower_bound(root,key);
    }

    int upper_bound(T key){
        return upper_bound(root,key);
    }

    int count(T key){
        return upper_bound(root,key)-lower_bound(root,key);
    }

    int size(){
        return (root?root->cnt:0);
    }

    T prod(int l,int r){
        return prod(root,l,r);
    }

    template<bool(*f)(T)>int max_right(int l){
        return max_right(l,[](T x){return f(x);});
    }

    template<class F>int max_right(int l,const F& f){
        assert(l<=cnt(root));
        T product=e();
        assert(f(product));
        Tree t1,t2;split_by_index(root,l,t1,t2);
        int res=l+max_right(t2,f,product);
        merge(root,t1,t2);
        return res;
        
    }

    template<bool (*f)(T)>int min_left(int r){
        return min_left(r,[](T x){return f(x);});
    }

    template<class F>int min_left(int r,const F& f){
        assert(r<=cnt(root));
        T product=e();
        assert(f(product));
        Tree t1,t2;split_by_index(root,r,t1,t2);
        int res=min_left(t1,f,product);
        merge(root,t1,t2);
        return res;
    }

    vector<T> to_vector(){
        vector<T> vec;to_vector(root,vec);
        return vec;
    }

    void dump(){
        dump(root);
        cout<<endl;
    }

    constexpr bool operator==(const SortedMultiList<T,op,e> &rhs)const noexcept{
        return to_vector()==rhs.to_vector();
    }
    constexpr bool operator!=(const SortedMultiList<T,op,e> &rhs)const noexcept{
        return to_vector()!=rhs.to_vector();
    }
};

struct Mo{
	private:
		struct Q{
			int x,y,id;
		};
		vector<Q> Queries;
	public:
		void add_query(int x,int y,int id){
			Queries.push_back({x,y,id});
		}
	
		/*
		prod [x,y) or [0,x),[0,y)
		*/
		template<class XP,class XM,class YP,class YM,class O>
		void solve(const int n,const XP& x_plus,const XM& x_minus,const YP& y_plus,const YM& y_minus,const O& out){
			int q=(int)Queries.size();
			int bs=n/min<int>(n,sqrt(q));
			sort(Queries.begin(),Queries.end(),[&](Q q1,Q q2)->bool {
				if(q1.x/bs<q2.x/bs)return 1;
				if(q1.x/bs==q2.x/bs){
					if(q1.x/bs&1)return q1.y<q2.y;
					else return q1.y>q2.y;
				}
				return 0;
			});
			int x=0,y=0;
			for(auto&&query:Queries){
				while(y<query.y)y_plus(y++);
				while(x>query.x)x_minus(--x);
				while(y>query.y)y_minus(--y);
				while(x<query.x)x_plus(x++);
				
				out(query.id);
			}
		}
	};

int op(int a,int b){return a+b;}
int e(){return 0;}

signed main(){
	int N,Q;cin>>N>>Q;
	vector<int> A(N);for(auto&&e:A)cin>>e;

	Mo mo;
	vector<int> X(Q);
	rep(i,Q){
		int l,r;cin>>l>>r;cin>>X[i];l--;
		mo.add_query(l,r,i);
	}

	SortedMultiList<int,op,e> tr;

	auto xp=[&](int i){
		tr.erase(A[i]);
	};

	auto xm=[&](int i){
		tr.insert(A[i]);
	};

	auto yp=[&](int i){
		tr.insert(A[i]);
	};

	auto ym=[&](int i){
		tr.erase(A[i]);
	};

	vector<int> ans(Q);

	auto out=[&](int id){
		// cout<<"id : ";
		// tr.dump();
		int idx=tr.lower_bound(X[id]);
		ans[id]+=X[id]*idx-tr.prod(0,idx);
		ans[id]+=tr.prod(idx,tr.size())-X[id]*(tr.size()-idx);
	};

	mo.solve(N,xp,xm,yp,ym,out);

	rep(i,Q)cout<<ans[i]<<"\n";
}