#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("distincte.in","r",stdin);\
              freopen("distincte.out","w",stdout);
#define CMAX 15485863
#define fastio std::ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define mp make_pair
#define INF 1e18
#define mod 666013
#define ll long long
#define SMAX 300
#define MAX 100000
#define pb push_back
#define add emplace_back
#define void inline void
using namespace std;
struct solve
{
    int first, second, third;
};
int n,k,m,sqr,v[MAX+5],ANS[MAX+5], tree[MAX*4+5], bk[MAX+5];
ll ans;
vector<solve> q;
inline bool cmp(solve a,solve b)
{
    return a.second < b.second;
}
void update(int st,int dr,int node,int pz,int val)
{
    if(st == dr)
    {
        tree[node] += val;
        return;
    }
    int mid = (st + dr) >> 1;
    if(pz <= mid) update(st,mid,(node<<1)+1,pz,val);
    else update(mid+1,dr,(node<<1)+2,pz,val);
    tree[node] = tree[(node<<1)+1] + tree[(node<<1)+2];
}
void query(int st,int dr,int node,int x,int y)
{
    if(x > y) return;
    if(st >= x && y >= dr)
    {
        ans += tree[node];
        return;
    }
    int mid = (st + dr) >> 1;
    if(x <= mid) query(st,mid,(node<<1)+1,x,y);
    if(mid < y) query(mid+1,dr,(node<<1)+2,x,y);
}
int main()
{
    fastio
    FILES
    cin >> n >> k >> m;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    for(int i = 1; i <= m; ++i)
    {
        int a,b;
        cin >> a >> b;
        q.pb({a,b,i});
    }
    sort(q.begin(),q.end(),cmp);
    int j = 0;
    for(int i = 1;i <= n; ++i)
    {
        if(bk[v[i]]) update(1,n,0,bk[v[i]],-v[i]);
        bk[v[i]] = i;
        update(1,n,0,i,v[i]);

        while(j < q.size() && q[j].second == i)
        {
            ans = 0;
            query(1,n,0,1,i);
            int g = ans;
            ans = 0;
            query(1,n,0,1,q[j].first-1);
            g -= ans;
            ANS[q[j].third] = g % mod;
            j++;
        }

    }
    for(int i = 1;i <= m; ++i)
        cout << ANS[i] << '\n';
}