#include <bits/stdc++.h>

using namespace std;

ofstream fout("distincte.out");

class InParser
{
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch()
    {
        ++sp;
        if (sp == 4096)
        {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume)
    {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n)
    {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n)
    {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

const int MOD = 666013;
const int NMAX = 100000;

int N, K, M;
int v[NMAX + 5];
int ans[NMAX + 5];
int frecv[NMAX + 5];
struct elem
{
    int idx;
    int st, dr;
    int sqrt_idx;
    bool operator < (const elem &other) const
    {
        return sqrt_idx < other.sqrt_idx;
    }
};
elem bucket[NMAX + 5];

int main()
{
    InParser fin("distincte.in");
    fin >> N >> K >> M;
    for(int i = 1; i <= N; i ++)
    {
        fin >> v[i];
    }
    const int block = sqrt(N);
    for(int i = 1; i <= M; i ++)
    {
        int l, r;
        fin >> l >> r;
        bucket[i].idx = i;
        bucket[i].st = l;
        bucket[i].dr = r;
        bucket[i].sqrt_idx = l / block;
    }
    sort(bucket + 1, bucket + M + 1);
    int suma = 0;
    for(int i = bucket[1].st; i <= bucket[1].dr; i ++)
    {
        if(frecv[v[i]] == 0)
        {
            suma += v[i];
            suma %= MOD;
        }
        frecv[v[i]] ++;
    }

    ans[bucket[1].idx] = suma;
    int st = bucket[1].st, dr = bucket[1].dr;
    for(int i = 2; i <= M; i ++)
    {
        while(st > bucket[i].st)
        {
            st--;
            if(frecv[v[st]] == 0)
            {
                suma += v[st];
                suma %= MOD;
            }
            frecv[v[st]]++;
        }
        while(st < bucket[i].st)
        {
            if(frecv[v[st]] == 1)
            {
                suma -= v[st];
                if(suma < 0)
                {
                    suma += MOD;
                }
            }
            frecv[v[st]] --;
            st ++;
        }
        while(dr < bucket[i].dr)
        {
            dr++;
            if(frecv[v[dr]] == 0)
            {
                suma += v[dr];
                suma %= MOD;
            }
            frecv[v[dr]] ++;
        }
        while(dr > bucket[i].dr)
        {
            if(frecv[v[dr]] == 1)
            {
                suma -= v[dr];
                if(suma < 0)
                {
                    suma += MOD;
                }
            }
            frecv[v[dr]]--;
            dr--;
        }
        ans[bucket[i].idx] = suma;
    }
    for(int i = 1; i <= M; i ++)
    {
        fout << ans[i] << '\n';
    }
    fout << '\n';
    return 0;
}