#include <bits/stdc++.h>
#define int long long
using namespace std;

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

const int NMAX = 100000;

int n, k, m;
vector < pair<int,int> > q[NMAX+1]; int st, dr;
int v[NMAX+1];
int deja[NMAX+1];
int aib[NMAX+1];
int rez[NMAX+1];
const int mod = 666013;

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

int sum(int p)
{
    int s = 0;
    for(;p>0;p-=(-p&p))
        s+=aib[p];
    return s;
}

signed main()
{
    fin >> n >> k >> m;
    for(int i=1; i<=n; i++)
        fin >> v[i];
    for(int i=1; i<=m; i++)
    {
        fin >> st >> dr;
        q[dr].push_back( make_pair(st,i) );
    }
    for(int i=1; i<=n; i++)
    {
        if(deja[v[i]] != 0)
            update(deja[v[i]], -1*v[i]);
        update(i,v[i]);
        deja[v[i]] = i;
        for(auto a : q[i])
            rez[a.second] = sum(i) - sum(a.first - 1);
    }

    for(int i=1; i<=m; i++)
        fout << rez[i]%mod << '\n';
    return 0;
}