#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

const long long nmax = 100005;
const long long mod = 666013;

struct query{
    long long st, dr, ind, sol;
}q[nmax];

long long n, m, a[nmax], aib[nmax], fr[nmax];

bool cmp(query x, query y){
    return x.dr < y.dr;
}

bool cmp2(query x, query y){
    return x.ind < y.ind;
}

long long ub(long long x){
    return (x&(-x));
}

void add(long long poz, long long val)
{
    for(long long i = poz; i <= n; i += ub(i))
        aib[i] = (aib[i] + val + mod) % mod;
}

long long sum(long long poz)
{
    long long res = 0;
    for(long long i = poz; i >= 1; i -= ub(i))
        res = (res + aib[i]) % mod;

    return res;
}

int main()
{
    f >> n >> m >> m;
    for(long long i = 1; i <= n; i ++)
        f >> a[i];

    for(long long i = 1; i <= n; i ++)
    {
        f >> q[i].st >> q[i].dr;
        q[i].ind = i;
    }

    sort(q + 1, q + m + 1, cmp);

    long long k = 1;
    for(long long i = 1; i <= n && k <= m; i ++)
    {
        add(i, a[i]);

        if(fr[a[i]])
            add(fr[a[i]], -a[i]);

        fr[a[i]] = i;

        if(i == q[k].dr)
            q[k].sol = (sum(i) - sum(q[k].st - 1) + mod) % mod, k ++;
    }

    sort(q + 1, q + m + 1, cmp2);

    for(long long i = 1; i <= m; i ++)
        g << q[i].sol << '\n';
    return 0;
}