#セグメント木
#　2**segsize が 配列の長さを超えるように
segsize=18
# 単位元
ident=[10**18]*10
# 用いる関数
def seg_f(X,Y):
    Ans=[]
    xp=0
    yp=0
    for i in range(10):
        if X[xp]<Y[yp]:
            Ans.append(X[xp])
            xp+=1
        else:
            Ans.append(Y[yp])
            yp+=1
    return Ans
        

Seg=[]
for i in range(segsize+1):
    Seg.append([ident]*(2**i))

def seg_add(key,num):
    Seg[-1][key]=seg_f(Seg[-1][key],num)
    seg_indd(key,segsize)

def seg_paste(key,num):
    Seg[-1][key]=num
    seg_indd(key,segsize)

def seg_indd(key,rank):
    if rank!=0:
        key=key//2*2
        Seg[rank-1][key//2]=seg_f(Seg[rank][key],Seg[rank][key^1])
        seg_indd(key//2,rank-1)

def seg_deel(A):
    for i in range(len(A)):
        seg_paste(i,A[i])


def seg_get(l,r=None):
    if r==None:
        r=l+1
    ansl=ident
    ansr=ident
    rank=segsize
    while rank>=0 and r!=l:
        if l%2==1:
            ansl=seg_f(ansl,Seg[rank][l])
            l+=1
        if r%2==1:
            ansr=seg_f(Seg[rank][r-1],ansr)
            r-=1
        l//=2
        r//=2
        rank-=1
    return seg_f(ansl,ansr)

n,Q=map(int,input().split())
A=list(map(int,input().split()))
for i in range(n):
    seg_paste(i+1,[A[i]]+[10**18]*9)


for i in range(Q):
    a,b,c=map(int,input().split())
    Ans=seg_get(a,b+1)
    #print(Ans)
    print(sum(Ans[:c]))