/*
ID: CipriFilipas
PROG: distincte
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stdio.h>

using namespace std;

FILE* fout = fopen("distincte.out", "wt");
void Read();
int Solve(int st, int dr, int sel[], int a[]);

int n, m, k;

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


void Read()
{
     FILE* fin = fopen("distincte.in", "rt");
     
     fscanf(fin, "%d %d %d", &n, &k, &m);
     int a[n+1];
     int sel[k+1];
     //fprintf(fout, "%d %d %d", m, n, k);
     
     for(int i = 1; i <= n; i++)
     {
             fscanf(fin, "%d", &a[i]);
             sel[a[i]] = 1;
     }
     for(int i = 1; i <= k; i++)
     {
             if(sel[i] == 0) sel[i] = -1;
             if(sel[i] == 1) sel[i] = 0;
     }
     
     int st, dr, val;     
     for(int i = 1; i <= m; i++)
     {
             fscanf(fin, "%d %d", &st, &dr);
             //fprintf(fout, "%d %d", st, dr);
             //val = Solve(st, dr, sel, a);
             fprintf(fout,"%d\n", (Solve(st, dr, sel, a)%666013));
             for(int i = 1; i <= n; i++)
             {
                     if(sel[a[i]] == -1) sel[a[i]] = -1;
                     if(sel[a[i]] == 1) sel[a[i]] = 0;
             }
     }
     fclose(fin);
     fclose(fout);
}

int Solve(int st, int dr, int sel[], int a[])
{
    int val = 0;
    for(int i = st; i <= dr; i++)
    {
            if(sel[a[i]] == 0) 
            {
                         val += a[i];
                         sel[a[i]] = 1;
            }
    }
    return val;
}