N,Q = map(int,input().split())
S = list(map(int,input().split()))
INFTY = 10**10
S = [INFTY]+S
A = [[] for _ in range(N+1)]
A[N] = [S[N]]
for i in range(N-1,0,-1):
    A[i] = A[i+1]+[S[i]]
    A[i] = sorted(A[i])
    if len(A[i])>10:
        A[i].pop()
K = 0
while 1<<K < N:
    K += 1
dp = [[[] for i in range(N+1)] for _ in range(K+1)]
for i in range(1,N+1):
    dp[0][i] = [S[i]]
for k in range(1,K+1):
    for i in range(1,N+1):
        if i+(1<<k)>N:
            dp[k][i] = A[i]
        else:
            dp[k][i] = dp[k-1][i]+dp[k-1][i+(1<<k-1)]
            dp[k][i] = sorted(dp[k][i])
            if len(dp[k][i])>10:
                dp[k][i] = dp[k][i][:10]
for _ in range(Q):
    L,R,M = map(int,input().split())
    R += 1
    d = R-L
    x = L
    B = []
    for i in range(K,-1,-1):
        if (d>>i) & 1:
            B += dp[i][x]
            B = sorted(B)
            if len(B)>M:
                B = B[:M]
            x += (1<<i)
    print(sum(B))