#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax = 100005;
const int mod = 666013;

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

int 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;
}

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

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

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

    return res;
}

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

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

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

    int k = 1;
    for(int i = 1; i <= n; 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(int i = 1; i <= m; i ++)
        g << q[i].sol << '\n';
    return 0;
}