#include <iostream>
#include <fstream>
#include <algorithm>
#define lsb(x) ((x^(x-1))&x)
#define MOD 666013
#define Nmax 100005
#define fs first
#define sf second.first
#define ss second.second

using namespace std;

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

pair <int, pair <int, int> > s[Nmax];
int n, m, k;
int aib[Nmax], a[Nmax];
int fr[Nmax], sum;
int ans[Nmax];


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

bool cmp(pair <int, pair <int, int> > a, pair <int, pair <int, int> > b)
{
    return a.sf < b.sf;
}

int query(int poz)
{
    int ans=0;
    for (; poz; poz-=lsb(poz))
    {
        ans+=aib[poz];
        ans%=MOD;
    }
    return ans;
}

void read()
{
    f >> n >> k >> m;
    for (int i = 1; i <= n; i++)
        f >> a[i];
    for (int i = 1; i <= m; i++)
    {
        f >> s[i].fs >> s[i].sf;
        s[i].ss=i;
    }
}

void solve()
{
    sort (s+1, s+m+1, cmp);
    int j = 1;
    for (int i = 1; i <= m; i++)
    {
        while (j <= s[i].sf)
        {
            update (j, a[j]);
            sum+=a[j];
            if (fr[a[j]])
            {
                update (fr[a[j]], -a[j]);
                sum-=a[j];
            }
            fr[a[j]]=j;
            j++;
        }
        int x = query(s[i].fs-1);
        ans[s[i].ss]=(sum-x+MOD)%MOD;
    }

    for (int i = 1; i <= m; i++)
        g << ans[i] << '\n';

}

int main()
{
    read();
    solve();
    return 0;
}