#include <bits/stdc++.h>
#define MOD 666013
#define maxN 100005
#define UB(x) ((x)&(-x))
using namespace std;
int n,m,j,k,i;
int poz[maxN];
int aib[maxN];
int sol[maxN];
struct quer
{
    int st,dr,ind;
}q[maxN];
int v[maxN];
class InputReader
{
public:
    InputReader() {}
    InputReader(const char *file_name)
    {
        input_file = fopen(file_name, "r");
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }
    inline InputReader &operator >>(int &n)
    {
        while(buffer[cursor] < '0' || buffer[cursor] > '9')
        {
            advance();
        }
        n = 0;
        while('0' <= buffer[cursor] && buffer[cursor] <= '9')
        {
            n = n * 10 + buffer[cursor] - '0';
            advance();
        }
        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE = 1 << 17;
    int cursor;
    char buffer[SIZE];
    inline void advance()
    {
        ++ cursor;
        if(cursor == SIZE)
        {
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
    }
};
bool cmp(quer a,quer b)
{
    return a.dr<b.dr;
}
void update(int pos,int val)
{
    int x;
    for(x=pos;x<=n;x+=UB(x))
        aib[x]=(aib[x]+val)%MOD;
}
int query(int pos)
{
    int s=0,x;
    for(x=pos;x>0;x-=UB(x))
        s=(s+aib[x])%MOD;
    return s;
}
int main()
{
    InputReader f("distincte.in");
    freopen("distincte.out","w",stdout);
    f>>n>>k>>m;
    for(i=1;i<=n;i++)
        f>>v[i];
    for(i=1;i<=m;i++)
    {
        f>>q[i].st>>q[i].dr;
        q[i].ind=i;
    }
    j=1;
    sort(q+1,q+m+1,cmp);
    for(i=1;i<=q[m].dr;i++)
    {
        if(poz[v[i]])
            update(poz[v[i]],-v[i]);
        update(i,v[i]);
        poz[v[i]]=i;
        while(i==q[j].dr)
        {
            sol[q[j].ind]=(query(q[j].dr)-query(q[j].st-1))%MOD;
            while(sol[q[j].ind]<0)
                sol[q[j].ind]+=MOD;
            j++;
        }
    }
    for(i=1;i<=m;i++)
        printf("%d\n",sol[i]);
    return 0;
}