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

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

const int NMAX = 100005,MOD = 666013;

int n,m,k,v[NMAX],aib[NMAX],last[NMAX],sol[NMAX];

vector < pair <int,int> > q[NMAX + 1];

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

int query(int poz)
{
    int sum = 0;
    for(int i = poz;i > 0;i -= i & -i)
        sum += aib[i],sum %= 666013;
    return sum;
}
int main()
{
    fin>>n>>k>>m;
    for(int i = 1;i <= n;i++)
    {
        fin>>v[i];
    }
    for(int i = 1;i <= m;i++)
    {
        int r,l;
        fin>>l>>r;
        pair <int,int> lemqq;
        lemqq.first = l;
        lemqq.second = i;
        q[r].push_back(lemqq);
    }
    for(int r = 1;r <= n;r++)
    {
        if(last[v[r]])
            update(last[v[r]],-v[r]);
        update(r,v[r]);
        last[v[r]] = r;
        for(auto i : q[r])
        {
            int left = i.first;
            int lemq = i.second;
            sol[lemq] = query(r) - query(left);
        }
    }
    for(int i = 1;i <= m;i++)
    {
        fout<<sol[i]<<"\n";
    }
    return 0;
}