#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100005;
const int MOD = 666013;

vector < pair<int,int> > v[NMAX];
int aib[NMAX],rasp[NMAX];
int a[NMAX],last[NMAX];
int n,k,m;

int q(int x)
{
    return (x&(-x));
}

void update(int poz,int val)
{
    for(int i=poz;i>=1;i-=q(i))
        aib[i]+=val;
}

int query(int poz)
{
    int rasp=0;
    for(int i=poz;i<=n;i+=q(i))
        rasp=(rasp+aib[i])%MOD;
    return rasp;
}

int main()
{
    fin >> n >> k >> m;
    for(int i=1;i<=n;i++) fin >> a[i];
    pair<int,int> aux;
    int y;
    for(int i=1;i<=m;i++)
    {
        fin >> aux.first >> y;
        aux.second=i;
        v[y].push_back(aux);
    }
    for(int i=1;i<=n;i++)
    {
        update(i,a[i]);
        update(last[a[i]],-a[i]);
        last[a[i]]=i;
        for(int j=0;j<v[i].size();j++)
            rasp[v[i][j].second]=query(v[i][j].first);
    }
    for(int i=1;i<=m;i++) fout << rasp[i] << '\n';
    return 0;
}