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

struct boi{
    int a,b;
};
const int MOD = 666013;
int aib[100005],v[100005],ans[100005],pas[100005],f[100005];
int n,m,p;
vector<boi>q[100005];
void update(int poz, int val)
{
    while(poz <= n)
    {
        aib[poz]=(aib[poz] + val)%MOD;
        poz+=(poz&(-poz));
    }
}

int solve(int poz)
{
    int sum = 0;
    while(poz)
    {
        sum=(sum + aib[poz])%MOD;
        poz-=(poz&(-poz));
    }
    return sum;
}
int main()
{
    ifstream cin ("distincte.in");
    ofstream cout ("distincte.out");
    cin>>n>>m>>p;
    for (int i = 1; i <= n; ++i)
    {
        cin>>v[i];
        pas[f[v[i]]]=i;
        if(f[v[i]]==0)
            update(i,v[i]);
        f[v[i]]=i;
    }
    for (int i=1;i<=p;++i){
        int x,y;
        cin>>x>>y;
        q[x].push_back({y,i});
    }

    for (int i=1;i<=n;++i)
    {
        if(i!=1&&pas[i-1]!= 0)
            update(pas[i-1],v[pas[i-1]]);
        for (auto j:q[t])
            ans[j.a]= (solve(j.b)-solve(i-1)+MOD)%MOD;
    }
    for (int i=1;i<=p;++i)
        cout<<ans[i]<<endl;
    return 0;
}