#include <fstream>
#include<algorithm>
using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");

struct cer
{
    int pozin, st, dr;
};

const int mod = 666013, nmax = 100005;
int st[nmax], dr[nmax];
int sol[nmax], query[nmax], aib[nmax], ante[nmax], v[nmax], n, k, m;

int zeros(int x)
{
    return (x ^ (x - 1)) & x;
}

void add(int x, int val)
{
    for(int i = x; i<=n; i += zeros(i))
        aib[i]=(aib[i] + val)%mod;
}

int calc(int x)
{
    int rez = 0;
    for(int i = x; i; i -= zeros(i))
        rez = (rez + aib[i])%mod;
    return rez;
}

inline bool cmp(const int &x,const int &y)
{
    return dr[x]<dr[y];
}

int main()
{
    int player_unu=0;

    in>>n>>k>>m;

    for(int i = 1; i<=n; i++)
        in>>v[i];

    for(int i = 1; i<=m; i++)
    {
        in>>st[i]>>dr[i];
        query[i] = i;
    }

    sort(query + 1,query + m + 1, cmp);

    for(int i = 1; i<=m; i++)
    {
        for(int j = dr[query[i - 1]] + 1; j<=dr[query[i]]; j++)
        {
            if(ante[v[j]])
            {
                add(ante[v[j]], -v[j]);
            }
            add(j, v[j]);
            ante[v[j]] = j;
        }

        sol[query[i]] = (calc(dr[query[i]]) - calc(st[query[i]] - 1))%mod;
    }

    for(int i = 1; i<=m; i++)
        out<<sol[i]<<'\n';

    return player_unu;
}