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

using namespace std;

const int mod = 786433;
const int root = 5;
const int root_1 = 471860;
const int root_pw = 1<<18;

long long q_pow(long long a, int k) {
    long long ans = 1;
    while (k) {
        if (k & 1) {
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        k >>= 1;
    }
    ans %= mod;
    return ans;
}

void fft (vector<long long> & a, bool invert) {
    int n = (int) 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) {
        int wlen = invert ? root_1 : root;
        for (int i=len; i<root_pw; i<<=1)
            wlen = int (wlen * 1ll * wlen % mod);
        for (int i=0; i<n; i+=len) {
            int w = 1;
            for (int j=0; j<len/2; ++j) {
                int u = a[i+j],  v = int (a[i+j+len/2] * 1ll * w % mod);
                a[i+j] = u+v < mod ? u+v : u+v-mod;
                a[i+j+len/2] = u-v >= 0 ? u-v : u-v+mod;
                w = int (w * 1ll * wlen % mod);
            }
        }
    }
    if (invert) {
        long long nrev = q_pow(n, mod - 2);
        for (int i=0; i<n; ++i)
            a[i] = int (a[i] * 1ll * nrev % mod);
    }
}

void multiply (const vector<long long>& a, const vector<long long>& b, vector<long long>& res) {
    vector<long long> 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]) % 786433;
    }
}

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;
}