#include <fstream>
#include <vector>
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
const long long mod = 666013;
const int N=2e5+5;
long long aib[N],n;
void update(int poz,long long val)
{
    for(int i=poz;i<=n;i+=(i&-i))
        aib[i]+=val;
}
long long query(int poz)
{
    long long suma=0;
    for(int i=poz;i>0;i-=(i&-i))
        suma+=aib[i];
    return suma;
}
long long v[N],k,q;
long long last[N];
long long ans[N];
struct qr
{
    int l,und;
};
vector<qr>adj[N];
int main()
{
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        adj[r].push_back({l,i});
    }
    for(int i=1;i<=n;i++)
    {
        if(last[v[i]]!=0)
        {
            update(last[v[i]],-v[i]);
        }
        update(i,v[i]);
        last[v[i]]=i;
        for(auto [st,u]:adj[i])
        {
            ans[u]=query(i)-query(st-1);
        }
    }
    for(int i=1;i<=q;i++)
        cout<<ans[i]%mod<<'\n';
    return 0;
}