#include <bits/stdc++.h>
using namespace std;
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;
    }
};
class OutParser
{
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch)
    {
        if (sp == 50000)
        {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        }
        else
        {
            buff[sp++] = ch;
        }
    }

public:
    OutParser(const char *name)
    {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser()
    {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser &operator<<(int vu32)
    {
        if (vu32 <= 9)
        {
            write_ch(vu32 + '0');
        }
        else
        {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser &operator<<(long long vu64)
    {
        if (vu64 <= 9)
        {
            write_ch(vu64 + '0');
        }
        else
        {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser &operator<<(char ch)
    {
        write_ch(ch);
        return *this;
    }
    OutParser &operator<<(const char *ch)
    {
        while (*ch)
        {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};
InParser f("distincte.in");
OutParser g("distincte.out");
const int mod = 666013;
int n, m, vmax, v[100001], cnt[100001];
struct query
{
    int st, dr, p;
} q[100001];
void add(int);
void remove(int);
long long rez, af[100001];
void change(int, int, int, int);
int main()
{
    f >> n >> vmax >> m;
    int dim = sqrt(n);
    for (int i = 1; i <= n; i++)
        f >> v[i];
    for (int i = 1; i <= m; i++)
        f >> q[i].st >> q[i].dr, q[i].p = i;
    sort(q + 1, q + m + 1, [dim](query a, query b) {
        int ax = a.st / dim, ay = b.st / dim;
        if (ax != ay)
            return ax < ay;
        if (ax & 1)
            return a.dr > b.dr;
        return a.dr < b.dr;
    });
    int st = 1, dr = 1;
    rez = v[1];
    cnt[v[1]] = 1;
    for (int i = 1; i <= m; i++)
    {
        int nst = q[i].st, ndr = q[i].dr;
        change(st, dr, nst, ndr);
        st = nst;
        dr = ndr;
        af[q[i].p] = rez % mod;
    }
    for (int i = 1; i <= m; i++)
        g << af[i] << '\n';
    return 0;
}
void add(int x)
{
    cnt[x]++;
    if (cnt[x] == 1)
        rez += x;
}
void remove(int x)
{
    cnt[x]--;
    if (cnt[x] == 0)
        rez -= x;
}
void change(int st, int dr, int nst, int ndr)
{
    if (dr <= nst || st >= ndr)
    {
        for (int i = st; i <= dr; i++)
            remove(v[i]);
        for (int i = nst; i <= ndr; i++)
            add(v[i]);
        return;
    }
    if (st < nst)
        for (int i = st; i < nst; i++)
            remove(v[i]);
    else
        for (int i = st - 1; i >= nst; i--)
            add(v[i]);
    if (dr < ndr)
        for (int i = dr + 1; i <= ndr; i++)
            add(v[i]);
    else
        for (int i = dr; i > ndr; i--)
            remove(v[i]);
}