#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("distincte.in");
ofstream cout("distincte.out");

const int NMAX = 100005,MOD = 666013;

int aib[NMAX],last[NMAX],v[NMAX],ans[NMAX],n,m,k;

struct INTERVAL
{
    int first,second,poz;
}events[NMAX];

bool cmp(INTERVAL x,INTERVAL y)
{
    if(x.first == y.first)
        return x.second < y.second;
    return x.first<y.first;
}

void update(int i,int val)
{
    for(;i <= n;i += i & (-i))
    {
        aib[i] = (aib[i] + MOD + val) % MOD;
    }
}

int querry(int poz)
{
    int sum = 0;
    for(;i > 0;i -= i & (-i))
    {
        sum = (sum + aib[i]) % MOD;
    }
    return sum;
}

int main()
{
    cin>>n>>k>>m;
    for(int i = 1; i <= n; i ++)
        cin>>v[i];
    for(int i = 1;i <= m;i++)
    {
        cin>>events[i].second>>events[i].first;
        events[i].poz = i;
    }
    sort(events + 1, events + m + 1,cmp);
    int last_poz = 1;
    for(int i = 1;i <= m;i++)
    {
        for(int j = last_poz;j <= events[i].first;j++){
            if(last[v[j]] != 0)
            {
                update(last[v[j]],-v[j]);
            }
            last[v[j]] = j;
            update(last[v[j]], v[j]);
        }
        last_poz = events[i].first;
        ans[events[i].poz] = querry(events[i].first) - querry(events[i].second - 1);
        if(ans[events[i].poz] < 0)
            ans[events[i].poz] += MOD;
    }
    for(int i = 1;i <= m;i++)
    {
        cout<<ans[i] % MOD<<'\n';
    }
    return 0;
}