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

const int N=100005,mod=666013;
int v[N],next[N],last[N],n,m,k;
long long aib[N],rez[N];
bool use[N];
struct Q
{
    int x,y,nr;
    bool operator<(const Q& X) const
    {
        return x<X.x || x==X.x && y<X.y;
    }
} Q[N];

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

inline int step(int& x)
{
    return x & (-x);
}

void update(int x,int val)
{
    for (;x<=n;x+=step(x))
        aib[x]+=val;
}

long long query(int x)
{
    long long rez=0;
    for (;x;x-=step(x))
        rez+=aib[x];
    return rez;
}

inline void activate(int x)
{
    use[x]=true;
    update(x,v[x]);
}

void elim(int x,int y)
{
    for (int i=x;i<=y;i++)
        if (use[i])
        {
            use[i]=false;
            update(i,-v[i]);
            if (next[i])
                activate(next[i]);
        }
}

int main()
{
    in>>n>>k>>m;
    for (int i=1;i<=n;i++)
        in>>v[i];
    for (int i=n;i;i--)
    {
        next[i]=last[v[i]];
        last[v[i]]=i;
    }
    for (int i=0;i<=k;i++)
        if (last[i])
        {
            update(last[i],i);
            use[last[i]]=true;
        }
    for (int i=1;i<=m;i++)
    {
        in>>Q[i].x>>Q[i].y;
        Q[i].nr=i;
    }
    sort(Q+1,Q+m+1);
    for (int i=1;i<=m;i++)
    {
        elim(Q[i-1].x,Q[i].x-1);
        rez[Q[i].nr]=query(Q[i].y);
    }
    for (int i=1;i<=m;i++)
        out<<rez[i]%mod<<"\n";
    return 0;
}