#include <fstream>
#include <vector>
using namespace std;

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

const int NMAX = 100005,MOD = 666013;

int n,m,k,v[NMAX],last[NMAX];
long long aib[NMAX],sol[NMAX];
vector < pair <long long,long long> > q[NMAX];

void update(int poz, int val)
{
    for(int i = poz;i <= n;i += i & -i)
        aib[i] += val + MOD,aib[i] %= MOD;
}

long long query(int poz)
{
    long long sum = 0;
    for(int i = poz;i > 0;i -= i & -i)
        sum += aib[i] + MOD,sum %= 666013;
    return sum;
}
int main()
{
    fin>>n>>k>>m;
    for(int i = 1;i <= n;i++)
    {
        fin>>v[i];
    }
    for(int i = 1;i <= m;i++)
    {
        int r,l;
        fin>>l>>r;
        pair <long long,long long> lemqq;
        lemqq.first = l;
        lemqq.second = i;
        q[r].push_back(lemqq);
    }
    for(int r = 1;r <= n;r++)
    {
        if(last[v[r]])
            update(last[v[r]],-v[last[v[r]]]);
        update(r,v[r]);
        last[v[r]] = r;
        for(auto i : q[r])
        {
            int left = i.first;
            int lemq = i.second;
            sol[lemq] = (query(r) - query(left - 1) + MOD)% MOD;
        }
    }
    for(int i = 1;i <= m;i++)
    {
        fout<<sol[i]<<"\n";
    }
    return 0;
}