#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int dim = 100005;
const int MOD = 666013;

struct quer
{
    int st,dr,idx;
}q[dim];

int a[dim],n,k,m,prv[dim];
long long sol[dim],aib[dim];

bool cmp(quer a,quer b)
{
    if (a.dr == b.dr)
    {
        return a.st < b.st;
    }
    return a.dr < b.dr;
}

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

long long int query(int poz)
{
    int s = 0;
    for (int i=poz; i>0; i-= i&(-i))
    {
        s = (aib[i] + s)%MOD;
    }
    return s;
}

int main()
{
    in >> n >> k >> m;
    for (int i=1; i<=n; i++)
    {
        in >> a[i];
        update(i,a[i]);
    }

    for (int i=1; i<=m; i++)
    {
        in >> q[i].st >> q[i].dr;
        q[i].idx = i;
    }
    sort(q+1,q+m+1,cmp);

    int j = 1;
    for (int i=1; i<=m; i++)
    {
        while (j <= q[i].dr)
        {
            if (prv[a[j]] != 0)
            {
                update(prv[a[j]] , -a[j]);
            }
            prv[a[j]] = j;
            j++;
        }
        sol[q[i].idx] = query(q[i].dr) - query(q[i].st-1);
    }
    for (int i=1; i<=m; i++)
    {
        out << sol[i]%MOD << "\n";
    }
    return 0;
}