#include <algorithm>
#include <cstdio>
#include <cstring>
#define zs(x) ((x)&(-(x)))

using namespace std;

const int N=100005, MOD=666013;

struct query{
    int x, y, p;
    bool operator <(const query &e) const
    {
        return y<e.y;
    }
};

class AIB{
private:
    int aib[N], n;
public:
    AIB(){n=0;memset(aib, 0, sizeof(aib));}
    AIB(const int _n) {n=_n;memset(aib, 0, sizeof(aib));}
    void set_size(const int _n) {n=_n;}
    void add(int i, const int val)
    {
        for(;i<=n;i+=zs(i)) aib[i]=(aib[i]+MOD+val)%MOD;
    }
    int operator[](int i) const
    {
        int ret=0;
        for(;i>0;i-=zs(i)) ret=(ret+MOD+aib[i])%MOD;
        return ret;
    }
};

int a[N], sol[N], lst[N];
query b[N];
AIB c;

int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    int n, m, q, i, j;
    scanf("%d%d%d", &n, &m, &q);
    c.set_size(n);
    for(i=1;i<=n;i++) scanf("%d", &a[i]);
    for(i=1;i<=q;i++)
    {
        scanf("%d%d", &b[i].x, &b[i].y);
        b[i].p=i;
    }
    sort(b+1, b+q+1);
    for(i=1;i<=q;i++)
    {
        for(j=b[i-1].y+1;j<=b[i].y;j++)
        {
            if(lst[a[j]]) c.add(lst[a[j]], -a[j]);
            c.add(j, a[j]);
            lst[a[j]]=j;
        }
        sol[b[i].p]=(c[b[i].y]-c[b[i].x-1]+MOD)%MOD;
    }
    for(i=1;i<=q;i++) printf("%d\n", sol[i]);
}