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

const int MAXS = 100000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    bitset<MAXS + 1> bs;
    bs[0] = 1;

    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        bs |= (bs << x);
    }

    vector<int> pref(MAXS + 1, 0);
    for (int i = 1; i <= MAXS; i++) {
        pref[i] = pref[i - 1] + bs[i];
    }

    while (Q--) {
        int L, R;
        cin >> L >> R;
        cout << pref[R] - pref[L - 1] << '\n';
    }

    return 0;
}