#include <fstream>
#include <cstring>
#define MAX 100001

using namespace std;

int n, m, k;
int e[MAX], a[MAX];
bool u[MAX];

void add(int x, int v);
int sum(int x);
int bit(int x);

int main()
{
    int i, j, v, s, s1, s2, v1, v2;
    
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");
    
    fin >> n >> k >> m;
    
    memset(a, 0, sizeof(a));
    
    for (i = 1; i <= n; i++)    
    {
        fin >> v;
        e[i] = v;
        add(i, v);
    }
    for (i = 1; i <= m; i++)
    {
        fin >> v1 >> v2;
        s1 = sum(v1-1);
        s2 = sum(v2);
        s = s2-s1;
        
        for (j = 1; j <= k; j++)
            u[j] = 0;
        for (j = v1; j <= v2; j++)    
            if (u[e[j]]) s -= e[j];
            else         u[e[j]] = 1;
        fout << s%666013 << "\n";
    }
    
    fout.close();
    fin.close();
    
    return 0;
}

void add(int x, int v)
{
    int i;
    for (i = x; i <= n; i += bit(i))     
        a[i] += v;
}

int sum(int x)
{
    int i, s = 0;
    for (i = x; i > 0; i -= bit(i))    
        s += a[i];
    return s;
}

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