#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int mod = 666013;
const int nmax = 1e5 + 5;
int v[nmax];

unordered_map<int,bool> Or(unordered_map<int,bool> &a, unordered_map<int,bool> &b)
{
    if(a.empty()) return b;
    if(b.empty()) return a;
    if(a.size() > b.size()) swap(a,b);
    for(auto [i,j] : a) b[i] = 1;
    return b;
}

int Sum(unordered_map<int,bool> a)
{
    int sum = 0;
    for(auto [i,j] : a)
    {
        sum += i * j;
        if(sum > mod) sum -= mod;
    }
    return sum;
}

struct SegTree{
    int next_power_of_2(int n)
    {
        int p = 1;
        while(p <= n) p *= 2;
        return p;
    }
    int offset;
    vector<unordered_map<int,bool> > aint;
    SegTree(int n)
    {
        offset = next_power_of_2(n);
        aint.resize(2*offset + 1);
    }
    void update(int pos, int val)
    {
        pos += offset;
        aint[pos][val] = 1;
        for(pos = pos / 2; pos > 0; pos /= 2)
        {
            aint[pos][val] = 1;
        }
    }
    unordered_map<int,bool> _query(int nod, int l, int r, int gl, int gr)
    {
        if(gr < l || r < gl)
        {
            unordered_map<int,bool> empty_map;
            return empty_map;
        }
        if(gl <= l && r <= gr)
        {
            unordered_map<int,bool> cop = aint[nod];
            return cop;
        }
        int mij = (l + r) / 2;
        unordered_map<int,bool> st = _query(2*nod,l,mij,gl,gr);
        unordered_map<int,bool> dr = _query(2*nod + 1,mij+1,r,gl,gr);
        return Or(st,dr);
    }

    int query(int i, int j)
    {
        return Sum(_query(1,0,offset-1,i,j));
    }
};

signed main()
{
    int n,m,k;
    fin>>n>>k>>m;
    SegTree st = SegTree(n);
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
        st.update(i,v[i]);
    }
    for(int i=1; i<=m; i++)
    {
        int a,b; fin>>a>>b;
        fout<<st.query(a,b)<<"\n";
    }
    return 0;
}