#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define mod 666013 

using namespace std;

ifstream in ("distincte.in");
ofstream out("distincte.out");

int n, k, m;
int bit[100100];
int a[100010];
int ap[100010];
int ans[100010];

void update (int i, int val)
{
    while (i <= n)
    {
        bit[i] += val;
        bit[i] %= mod;
        i += (i & -i);
    }
}
int ps(int i)
{
    int sum = 0;
    while (i > 0)
    {
        sum += bit[i];
        i -= (i & -i);
        sum %= mod;
    }
    return sum;
}
int rangeSum(int i, int j){
    return ps(j) - ps(i - 1);
}

struct query {
    int st, dr, index;
};

bool cmp (query x, query y)
{
    return x.dr < y.dr || (x.st < y.st && x.dr == y.dr);
}

query q[100100];

int main ()
{
    in >> n >> k >> m;
        
    for (int i = 1; i <= n; i++)
    {
        in >> a[i];
    }
    for (int i = 1; i <= m; i ++)
    {
        in >> q[i].st >> q[i].dr;
        q[i].index = i;
    }
    sort (q + 1, q + m + 1, cmp);
    
    int last = 1;
    for (int i = 1; i <= m; i ++)
    {
      
        for (int j = last; j <= q[i].dr; j++)
        {
            if (ap[a[j]]){
                update (ap[a[j]], -a[j]);
            }
            ap[a[j]] = j;
            update (j, a[j]);
        }
        ans[q[i].index] = rangeSum(q[i].st, q[i].dr);
        if (ans[q[i].index] < 0)
        {
            ans[q[i].index] += mod;
        }
        last = q[i].dr;
    }
    for (int i = 1; i <= m; i++)
    {
        out << ans[i] << "\n";
    }

}