#ifndef LOCAL
    #pragma GCC optimize("O3")
    #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const int NMAX = 1e5 + 5;
const int MOD = 666013;
/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("distincte.in");
    ofstream out("distincte.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

int N, K, Q;
int v[NMAX], rasp[NMAX];
int block;

struct Query
{
    int st, dr, idx;

    bool operator < (const Query &other) const
    {
        if (st / block == other.st / block)
            return dr < other.dr;
        
        return st / block < other.st / block;
    }
};

vector <Query> queries;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> N >> K >> Q;

    for (int i = 0 ; i < N ; ++ i)
        cin >> v[i];

    int a, b;
    for (int i = 0 ; i < Q ; ++ i)
    {
        cin >> a >> b;

        queries.push_back({a - 1, b - 1, i});
    }
}
///-------------------------------------
inline void Solution()
{
    block = sqrt(N);
    sort(queries.begin(), queries.end());

    unordered_map <int, int> mapa;

    int st = 0, dr = 0, suma = 0;
    for (auto q: queries)
    {
        while (st < q.st)
        {
            mapa[v[st]] --;
            if (!mapa[v[st]]) suma -= v[st] % MOD;
            if (suma < 0) suma += MOD;
            st ++;
        }

        while (st > q.st)
        {
            mapa[v[st]] ++;
            if (mapa[v[st]] == 1) suma += v[st] % MOD;
            if (suma >= MOD) suma -= MOD;
            st --;
        }

        while (dr <= q.dr)
        {
            mapa[v[dr]] ++;
            if (mapa[v[dr]] == 1) suma += v[dr] % MOD;
            if (suma >= MOD) suma -= MOD;
            dr ++;
        }

        while (dr > q.dr + 1)
        {
            mapa[v[dr]] --;
            if (!mapa[v[dr]]) suma -= v[dr] % MOD;
            if (suma < 0) suma += MOD;
            dr --;
        }

        rasp[q.idx] = suma;
    }
}
///-------------------------------------
inline void Output()
{
    for (int i = 0 ; i < Q ; ++ i)
        cout << rasp[i] << "\n";
}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}