import sys sys.setrecursionlimit(10**7) def ii(): return int(input()) def mi(d=0): return map(lambda x:int(x)-d,input().split()) INF = float("inf") MOD = 998244353 def answer(s): print(s) exit() def cross(xy): x,y = xy return (x+1,y),(x-1,y),(x,y+1),(x,y-1) ################################################ class FenwickTree: def __init__(self,size): self.size = size self.arr = [0]*size self.count = [0]*size def sum(self,index): s = 0 index += 1 while index>0: s += self.arr[index-1] index -= index&(-index) return s def add(self,index,value): i = index+1 while i<=self.size: self.arr[i-1] += value self.count[i-1] += 1 i += i&(-i) def countRange(self,left,right): l,r = left+1,right+1 lc,rc = 0,0 while l > 0: lc += self.count[l-1] l -= l&(-l) while r > 0: rc += self.count[r-1] r -= r&(-r) return rc-lc n,q = mi() a = list(map(lambda x:(int(x[1]),x[0]),enumerate(input().split()))) rs = [0] for aa in a: rs.append(rs[-1] + aa[0]) a.sort() query = [] for qi in range(q): query.append((list(mi()),qi)) query.sort(key=lambda x:x[0][2]) # print(query) ai = 0 tree = FenwickTree(n) ans = [0]*q for qq,qi in query: l,r,x = qq while ai < n and a[ai][0] <= x: aa,index = a[ai] ai += 1 tree.add(index,aa) count = tree.countRange(l-2,r-1) small = tree.sum(r-1) - tree.sum(l-2) big = rs[r]-rs[l-1] - small # print(small,big,count) ans[qi] = x*count-small + big-x*(r-l+1-count) # print(tree.arr) for aa in ans: print(aa)