#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 100003
#define MOD 666013
#define db 0
using namespace std;
int a[NMAX], aib[NMAX], sol[NMAX], f[NMAX];
int n, m, k;
struct str 
{
    int x, y, p;
};
str v[NMAX];
bool cmp (str a, str b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}
int lsb (int x)
{
    return (x & (-x));
}
void update (int poz, int x)
{
    while (poz <= n)
    {
        aib[poz] = (aib[poz] + x) % MOD;
        poz += lsb (poz);
           
    }
   
}
int query (int poz)
{
    
    int sol = 0;
    while (poz > 0)
    {
        sol = (sol + aib[poz]) % MOD;
        poz -= lsb(poz);
    }
    return sol;
}
int main()
{
    ifstream cin ("distincte.in");
    ofstream cout ("distincte.out");
    cin >> n >> k >>  m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        cin >> v[i].x >> v[i].y;
        v[i].p = i;

    }
    sort (v + 1, v + 1 + m, cmp);
    int j = 1;

    for (int i = 1; i <= n; i++)
    {
       if (f[a[i]] == 0)
       {
           f[a[i]] = i;
           update(i, a[i]);
       }
       else
       {
           update (f[a[i]], - a[i]);
           update (i, a[i]);
           f[a[i]] = i;
           
       }
       //cout << "Q =" << query(i) << "\n"; 
       while ( v[j].y == i)
       {
           sol[v[j].p] = (query (i) - query (v[j].x - 1)) % MOD; 
           if (sol[v[j].p] < 0)
               sol[v[j].p] = (sol[v[j].p] + MOD) % MOD;
           j++;
       }
       if (j > m)
           break;
       

   }
   for (int i = 1; i <= m; i++)
       cout << sol[i] << "\n";
   return 0;
}