#include <fstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
#define NMAX 100005

int v[NMAX];
int aib[NMAX];
map<int, int> used;
int n;
#define MOD 666013
map<int, vector<pair<int, int>>> mp;
int ans[NMAX];
pair<int, int> q[NMAX];
bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.second < b.second;
}
void update(int pos, int val)
{
    val %= MOD;
    if (val < 0)
        val += MOD;
    for (int i = pos; i <= n; i += i & (-i))
    {
        aib[i] += val;
        aib[i] %= MOD;
    }
}
int query(int pos)
{
    int r = 0;
    for (int i = pos; i >= 1; i -= i & (-i))
    {
        r += aib[i];
        r %= MOD;
    }
    return r;
}
int main()
{
    int k, m;
    fin >> n >> k >> m;
    for (int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        mp[b].push_back({a, i});
    }
    for (int i = 1; i <= n; i++)
    {

        update(i, v[i]);
        if (used[v[i]])
        {
            update(used[v[i]], -v[i]);
        }
        used[v[i]] = i;
        for (auto &j : mp[i])
        {
            ans[j.second] = (query(i) - query(j.first - 1) + MOD) % MOD;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        fout << ans[i] << '\n';
    }
    return 0;
}