#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013
#define fs first
#define sc second
#define lsb(i) ( i & (-i) )

using namespace std;

typedef long long LL;
typedef pair<int, int> pereche;
typedef pair<pereche, int> triplet;

int n, k, m, i, j, rgt;
int sol[100005];
int lst[100005];
int v[100005];
triplet qry[100005];
int aib[100005];

class Reader
{
private:
    char buff[100805];
    int buffer, cnt;

public:
    Reader()
    {
        buffer = 1 << 15;
        cnt = buffer - 1;
    }

    char gChar()
    {
        if(++cnt == buffer)
        {
            cnt = 0;
            fread(buff, buffer, 1, stdin);
        }
        return buff[cnt];
    }

    int gInt()
    {
        int nr = 0;
        char ch = gChar();
        while(ch < '0' || '9' < ch)
            ch = gChar();
        while('0' <= ch && ch <= '9')
        {
            nr = nr * 10 + ch - '0';
            ch = gChar();
        }
        return nr;
    }
};
Reader rdr;

void U(int pos, int val)
{
    for(int i = pos; i <= n; i += lsb(i))
        aib[i] = (aib[i] + val + mod) % mod;
}

int Q(int pos)
{
    int sum = 0;
    for(int i = pos; i >= 1; i -= lsb(i))
    {
        sum = (sum + aib[i]);
        if(sum >= mod)
            sum -= mod;
    }
    return sum;
}

int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);

    //scanf("%d%d%d", &n, &k, &m);
    n = rdr.gInt();
    k = rdr.gInt();
    m = rdr.gInt();

    for(i = 1; i <= n; i++)
        v[i] = rdr.gInt();

    for(i = 1; i <= m; i++)
    {
        //scanf("%d%d", &qry[i].fs.sc, &qry[i].fs.fs);
        qry[i].fs.sc = rdr.gInt();
        qry[i].fs.fs = rdr.gInt();
        qry[i].sc = i;
    }

    sort(qry + 1, qry + m + 1);

    rgt = 0;
    for(i = 1; i <= m; i++)
    {
        for(j = rgt + 1; j <= qry[i].fs.fs; j++)
        {
            if(lst[ v[j] ])
                U(lst[ v[j] ], -v[j]);

            lst[ v[j] ] = j;
            U(j, v[j]);
        }
        rgt = qry[i].fs.fs;

        sol[ qry[i].sc ] = Q( qry[i].fs.fs ) - Q( qry[i].fs.sc - 1 );
        if(sol[ qry[i].sc ] < 0)
            sol[ qry[i].sc ] += mod;
    }

    for(i = 1; i <= m; i++)
        printf("%d\n", sol[i]);

    return 0;
}