import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Queue;
import java.util.Random;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.Predicate;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
    static MyPrintWriter pw = MyPrintWriter.getInstance();

    static FastScanner sc = FastScanner.getInstance();

    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        new Main().run();
        pw.flush();
    }

    void run() {
        int N = sc.nextInt();
        int Q = sc.nextInt();
        int[] S = sc.nextInts(N);
        var wm = new WaveletMatrix(S);
        for (int QUERY = 0; QUERY < Q; QUERY++) {
            int L = sc.nextInt() - 1;
            int R = sc.nextInt();
            int K = sc.nextInt();
            long ans = 0;
            for (int i = 0; i < K; i++) {
                ans += wm.quantile(L, R, i);
            }
            pw.println(ans);
        }
    }
}

class ArrayUtils {
    /**
     * 空のときはInteger.MAX_VALUE
     *
     * @param a
     * @return  */
    public static int min(int[] a) {
        int ret = Integer.MAX_VALUE;
        for (int i = 0; i < a.length; ++i) {
            ret = Math.min(ret, a[i]);
        }
        return ret;
    }

    public static int max(int... a) {
        int ret = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; ++i) {
            ret = Math.max(ret, a[i]);
        }
        return ret;
    }
}

class BitArray {
    final int n;

    final int lg = 5;

    final int wordSize = 1 << lg;

    final int mask = (1 << lg) - 1;

    final int[] prefixSum;

    final int[] data;

    final int len;

    public BitArray(int n) {
        this.n = n;
        len = ((n + wordSize) - 1) / wordSize;
        data = new int[len + 1];// prefixSum(i)でi=a.lengthが飛んでくる場合があるので、1つ大きめに取っている。

        prefixSum = new int[data.length + 1];
    }

    public void set(int k) {
        data[k >> lg] |= 1 << (k & mask);
    }

    public void build() {
        for (int i = 1; i < data.length; i++) {
            prefixSum[i] = Integer.bitCount(data[i - 1]) + prefixSum[i - 1];
        }
    }

    /**
     * [0, i)の和を返す
     *
     * @param i
     * @return  */
    public int prefixSum(int i) {
        return prefixSum[i >> lg] + Integer.bitCount(data[i >> lg] & ((1 << (i & mask)) - 1));
    }

    /**
     * 内部状態を文字列として表現します。
     *
     * <p>計算量: $O(\text{len})$</p>
     *
     * @return 内部状態の文字列表現
     */
    // 未テスト
    @Override
    public String toString() {
        return ((((("BitArray{n=" + n) + ", data=") + Arrays.toString(data)) + ", prefixSum=") + Arrays.toString(prefixSum)) + "}";
    }
}

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1 << 16];

    private int ptr = 0;

    private int buflen = 0;

    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
            ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            // n = n * 10 + (b - '0');
            n = ((n << 1) + (n << 3)) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }

    public int nextInt() {
        return ((int) (nextLong()));
    }

    public int[] nextInts(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = nextInt();
        }
        return a;
    }
}

class Ints {
    public static int bitAt(int binary, int pos) {
        if (pos >= 32) {
            return 0;
        }
        return (binary >>> pos) % 2;
    }
}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }
}

class WaveletMatrix {
    int w;// 何bit使うか


    final int n;

    final BitArray[] rank1;

    final int[] mid;// mid[i]=iビット目が0であるものの個数


    int[] inverseMapping;

    final long maxA;

    public WaveletMatrix(int[] a) {
        if (ArrayUtils.min(a) < 0) {
            throw new AssertionError();
        }
        n = a.length;
        maxA = ArrayUtils.max(a);
        w = 1;
        while ((1L << w) <= maxA) {
            w++;
        } 
        rank1 = new BitArray[w];
        mid = new int[w];
        int[] sorted = new int[n];
        Arrays.setAll(sorted, i -> a[i]);
        inverseMapping = new int[n];
        Arrays.setAll(inverseMapping, i -> i);
        for (int i = w - 1; i >= 0; --i) {
            rank1[i] = new BitArray(n);
            for (int j = 0; j < n; j++) {
                if (Ints.bitAt(sorted[j], i) == 1) {
                    rank1[i].set(j);
                }
            }
            rank1[i].build();
            int[] nsorted = new int[n];
            int[] nInverseMapping = new int[n];
            int pointer = 0;
            // wビット目でボックスソート
            for (int j = 0; j < n; j++) {
                if (Ints.bitAt(sorted[j], i) == 0) {
                    nsorted[pointer] = sorted[j];
                    nInverseMapping[pointer++] = inverseMapping[j];
                }
            }
            mid[i] = pointer;
            for (int j = 0; j < n; j++) {
                if (Ints.bitAt(sorted[j], i) == 1) {
                    nsorted[pointer] = sorted[j];
                    nInverseMapping[pointer++] = inverseMapping[j];
                }
            }
            sorted = nsorted;
            inverseMapping = nInverseMapping;
        }
    }

    /**
     * height+1, height+2, .., w-1番目までのbitを用いてソートしたとき、ソート後のa[0, i)のheight番目のbitにvは何個含まれているかを返す。
     *
     * @param i
     * @param v
     * @param height
     * @return  */
    private final int rank(int i, int v, int height) {
        if (i <= 0) {
            return 0;
        }
        return v == 1 ? rank1[height].prefixSum(i) : i - rank1[height].prefixSum(i);
    }

    /**
     * a[l, r) における k 番目 (0-indexed) に小さい値を返す。
     * verified:https://atcoder.jp/contests/abc431/submissions/70815921
     */
    public final long quantile(int l, int r, int k) {
        if ((l >= r) || ((r - l) <= k)) {
            throw new AssertionError();
        }
        return quantile(l, r, k, w - 1);
    }

    /**
     * height+1,height+2,..,w-1番目のビットを用いてソートしたとき、ソート後のaでk番目(0-indexed)に小さい数を返す
     *
     * @param l
     * @param r
     * @param k
     * @param height
     * @return verified:https://atcoder.jp/contests/abc431/submissions/70815921
     */
    private final long quantile(int l, int r, int k, int height) {
        // 上のビットから順に決める
        long ret = 0;
        for (int h = height; h >= 0; h--) {
            int l0 = rank(l, 0, h);
            int r0 = rank(r, 0, h);
            int nz = r0 - l0;
            if ((nz - 1) >= k) {
                // heightビット目が0確定
                l = l0;
                r = r0;
            } else {
                // heightビット目が1確定
                ret |= 1L << h;
                l += mid[h] - l0;
                r += mid[h] - r0;
                k -= nz;
            }
            // heightビット目でソートする。
        }
        return ret;
    }
}


// --- Original Code ---
// 
// 
// import java.io.IOException;
// import java.util.Arrays;
// 
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.fold.WaveletMatrix;
// 
// public class Main {
// 	static MyPrintWriter pw = MyPrintWriter.getInstance();
// 	static FastScanner sc = FastScanner.getInstance();
// 
// 	public static void main(String[] args) throws IOException {
// 		new Main().run();
// 		pw.flush();
// 		MergeFiles.export();
// 	}
// 	
// 
// 	void run() {
// 		int N=sc.nextInt();
// 		int Q=sc.nextInt();
// 		int[]S=sc.nextInts(N);
// 		var wm=new WaveletMatrix(S);
// 		for (int QUERY = 0; QUERY < Q; QUERY++) {
// 			int L=sc.nextInt()-1;
// 			int R=sc.nextInt();
// 			int K=sc.nextInt();
// 			long ans=0;
// 			for (int i = 0; i < K; i++) {
// 				ans+=wm.quantile(L, R, i);
// 			}
// 			pw.println(ans);
// 		}
// 	}
//     
// 	void tr(Object... objects) {
// 		System.out.println(Arrays.deepToString(objects));
// 	}
// }
//