#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;
        if (aib[poz] < 0)
            aib[poz] = (aib[poz] + MOD) % MOD;
   //     cout << poz << " ";
        poz += lsb (poz);
           
    }
   
}
int query (int poz)
{
    int ok = 0;
    int sol = 0;
    while (poz > 0)
    {
        sol = (sol + aib[poz]) % MOD;
        poz -= lsb(poz);
        if (ok) 
            cout << poz << " PLM ";
    }
    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 <= m; i++)
        cout << v[i].x << " " << v[i].y << endl;
    for (int i = 1; i <= n; i++)
    {
       if (f[a[i]] == 0)
       {
           f[a[i]] = i;
           update(i, a[i]);
//           cout << f[a[i]] << " " << a[i] << endl;
       }
       else
       {
           if (db)

           cout <<"\n\n\n\n"<< query (i) << " i = " << i  <<endl;
                
           update (f[a[i]], - a[i]);
           if (db)
           cout << "AFTER FIRST UPDATE" << query(i) <<endl;
           update (i, a[i]);
           if (db)
           cout << "AFTER SECOND" << query (i) << endl;
           f[a[i]] = i;
           
       }
       if (db)
       cout << "QUERRY " << i << ": " << query(i) << endl;
       if ( v[j].y == i)
       {
           sol[v[j].p] = query (i) - query (v[j].x - 1); 
           if (sol[v[j].p] < 0)
               sol[v[j].p] = (sol[v[j].p] + MOD) % MOD;
           j++;
       }
       

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