#include <memory>
#include <cstddef>
#include <iostream>
#include <string>
#include <complex>
#include <vector>
#include <cmath>
#include <numbers>

using namespace std;

using base = complex<long double>;

void fft(vector<base>& a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j >= bit; bit >>= 1) {
            j -= bit;
        }
        j += bit;
        if (i < j) {
            swap(a[i], a[j]);
        }
    }

    for (int len=2; len<=n; len<<=1) {
        long double ang = 2*numbers::pi/len * (invert ? -1 : 1);
        base wlen (cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            base w(1);
            for (int j = 0; j < len/2; ++j) {
                base u = a[i+j],  v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert) {
        for (int i = 0; i < n; ++i) {
            a[i] /= n;
        }
    }
}

void multiply (const vector<long long>& a, const vector<long long>& b, vector<long long>& res) {
    vector<base> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < max(a.size(), b.size())) {
        n <<= 1;
    }
    n <<= 1;
    fa.resize(n), fb.resize(n);

    fft(fa, false), fft(fb, false);
    for (int i = 0; i < n; ++i) {
        fa[i] *= fb[i];
    }
    fft(fa, true);

    res.resize(min(n, int(5e4 + 1)));
    for (int i = 0; i < res.size(); ++i) {
        res[i] = (long long)(fa[i].real() + 0.5);
    }
}

vector<long long> poww(vector<long long>& a, int k) {
    vector<long long> ans = {1};
    while (k) {
        if (k & 1) {
            multiply(ans, a, ans);
        }
        multiply(a, a, a);
        k >>= 1;
    }
    return ans;
}

int c_i[50007];

int main() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<long long> goods;
    int max_c = -1;
    for (int i = 0; i < n; ++i) {
        int c;
        cin >> c;
        c_i[c]++;
        max_c = max(max_c, c);
    }
    for (int i = 0; i <= max_c; ++i) {
        goods.push_back(c_i[i]);
    }
    goods = poww(goods, k);
//    for (int i = 0; i < goods.size(); ++i) {
//        cout << goods[i] << "x^" << i << " ";
//    }
//    cout << "\n";
    goods.resize(50002);
    vector<long long> prefix;
    int curr = 0;
    for (int i = 0; i < goods.size(); ++i) {
        curr += goods[i];
        curr %= 786433;
        prefix.push_back(curr);
    }
//    for (int i : prefix) {
//        cout << i << " ";
//    }
//    cout << "\n";
//    cout << q << "\n";
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l;
        cout << (prefix[r] - prefix[l] + 786433) %  786433 << "\n";
    }
    return 0;
}