/*
    Worg
*/
#include <cstdio>
#include <algorithm>
#define zeros(x) ((x ^ (x - 1)) & x)
#define DIM 100100
#define MOD 666013
using namespace std;
FILE *fin=freopen("distincte.in","r",stdin);
FILE *fout=freopen("distincte.out","w",stdout);

int n, k, m;
int AIB[DIM];
int v[DIM], viz[DIM];
struct type {
                int left, right, ord;
            };
type question[DIM];
pair <int,int> ans[DIM];

inline bool comp(type a, type b)
{
    if( a.right == b.right )
        return a.left < b.left;
    return a.right < b.right;
}

inline void Add(int pos, int val)
{
    int i;
    for(i = pos; i <= n; i += zeros(i))
        AIB[i] += val;
}

inline int Query(int pos)
{
    int i, ret = 0;
    for(i = pos; i; i -= zeros(i))
        ret = (ret + AIB[i]) % MOD;
    return ret;
}

void Read()
{
    int i;
    scanf("%d %d %d", &n, &k, &m);
    for(i = 1; i <= n; ++i)
        scanf("%d ", &v[i]);
    for(i = 1; i <= m; ++i)
    {
        scanf("%d %d", &question[i].left, &question[i].right);
        question[i].ord = i;
    }
    sort(question + 1, question + m + 1, comp);
}

void Solve()
{
    int i, pos;
    pos = 1;
    for(i = 1; i <= m; ++i)
    {
        for(; pos <= question[i].right; ++pos)
        {
            if( viz[ v[pos] ] )
                Add( viz[ v[pos] ], -v[pos] );
            Add(pos, v[pos]);
            viz[ v[pos] ] = pos;
        }
        ans[i].first = question[i].ord;
        ans[i].second = (Query(question[i].right) - Query(question[i].left - 1) + MOD) % MOD;
    }
    sort(ans + 1, ans + m + 1);
    for(i = 1; i <= m; ++i)
        printf("%d\n", ans[i].second);
}

int main()
{
    Read();
    Solve();
    return 0;
}