#include<fstream>
#include<unordered_map>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;

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

const int NMAX = 1e5 + 1;
const int MOD = 666013;

int ap[NMAX],v[NMAX],ans[NMAX],f[NMAX];

struct query
{
    int st,dr,id;
    bool operator <(const query lhs) const
    {
        return lhs.dr > dr;
    }
};

vector<query> queries[500];

int main()
{

    int n,m,q,a,b,c,baka; cin >> n >> baka >> q;
    int block = ceil(sqrt(n)); if(block == 1) block = 2;
    for(int i = 1; i <= n ; i++)
        {
            ap[i] = ap[i - 1];
            if(i % block == 1) ap[i]++;
            cin >> v[i];
        }

    for(int i = 1; i <= q ; i++)
        {
            cin >> a >> b;
            queries[ap[a]].push_back({a,b,i});
        }

    for(int i = 1; i <= ap[n] ; i++)
        {
            if(queries[i].empty()) continue;
            sort(queries[i].begin(),queries[i].end());
            int stanga = queries[i][0].st,dreapta = queries[i][0].dr , suma = 0;

            for(int i = 1; i <= baka ; i++) f[i] = 0;

            for(int i = stanga ; i <= dreapta ; i++)
                {
                    int &ad = f[v[i]]; ad++;
                    if(ad == 1)
                        {
                            suma += v[i];
                            if(suma > MOD) suma -= MOD;
                        }
                }

            ans[queries[i][0].id] = suma;

            for(int j = 1; j < queries[i].size() ; j++)
                {
                    query &now = queries[i][j];
                    if(now.dr < dreapta) exit(1);
                    while(dreapta < now.dr)
                        {
                            dreapta++;
                            int &ad = f[v[dreapta]]; ad++;
                            if(ad == 1)
                                {
                                    suma += v[dreapta];
                                    if(suma > MOD) suma -= MOD;
                                }
                        }

                    while(stanga < now.st)
                        {
                            int &ad = f[v[stanga]]; ad--;
                            if(ad == 0)
                                {
                                    suma -= v[stanga];
                                    if(suma < 0) suma += MOD;
                                }

                            stanga++;

                        }

                    while(stanga > now.st)
                        {
                            stanga--;
                            int &ad = f[v[stanga]]; ad++;
                            if(ad == 1)
                                {
                                    suma += v[stanga];
                                    if(suma > MOD) suma -= MOD;
                                }

                        }

                    ans[now.id] = suma;
                }


        }

    for(int i = 1; i <= q ; i++) cout << ans[i] << '\n';
}