#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back
#define mt make_tuple

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()
#define uniq(x) unique(all(x)), x.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T, size_t N>
void re(array <T, N>& x);
template <class T> 
void re(vt <T>& x);

template <class T> 
void re(T& x) {
    cin >> x;
}

template <class T, class... M> 
void re(T& x, M&... args) {
    re(x), re(args...);
}

template <class T> 
void re(vt <T>& x) {
    for(auto& it : x) re(it);
}

template <class T, size_t N>
void re(array <T, N>& x) {
    for(auto& it : x) re(it);
}

template <class T, size_t N>
void wr(const array <T, N>& x);
template <class T> 
void wr(const vt <T>& x);

template <class T> 
void wr(const T& x) {
    cout << x;
}

template <class T, class ...M>  
void wr(const T& x, const M&... args) {
    wr(x), wr(args...);
}

template <class T> 
void wr(const vt <T>& x) {
    for(auto it : x) wr(it, ' ');
}

template <class T, size_t N>
void wr(const array <T, N>& x) {
    for(auto it : x) wr(it, ' ');
}

template<class T, class... M>
auto mvt(size_t n, M&&... args) {
    if constexpr(sizeof...(args) == 1)
        return vector<T>(n, args...);
    return vector(n, mvt<T>(args...));
}

void set_fixed(int p = 0) {
    cout << fixed << setprecision(p);
}

void set_scientific() {
    cout << scientific;
}

void Open(const string& name) {
#ifndef ONLINE_JUDGE
    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
#endif
}

struct BIT {
    const int mod = 666013;
    int n;
    vt <int> t;

    BIT() {}
    BIT(int _n) {
        n = _n;
        t.resize(n + 10);
    }

    void init(int _n) {
        n = _n;
        t.resize(n + 10);
    }

    void build(const vt <int>& a) {
        for (int i = 0; i < n; ++i)
            t[i + 1] = a[i];

        for (int i = 1; i <= n; ++i) {
            int p = i + (i & -i);
            if (p <= n) {
                t[p] = t[p] + t[i];
            }
        }
    }

    void upd(int idx, int add) {
        add = (add % mod + mod) % mod;
        for (;idx <= n; idx += (idx & -idx))
            t[idx] = (t[idx] + add) % mod;
    }

    ll query(int idx) {
        ll sum = 0;
        for (; idx >= 1; idx -= (idx & -idx))
            sum = (sum + t[idx]) % mod;
        return sum;
    }

    ll query(int l, int r)  {
        return ((query(r) - query(l - 1)) % mod + mod) % mod;
    }

    int kth(ll target) {
        int l = 1, r = n;
        while (l <= r) {
            int m = l + (r - l) / 2;

            if (query(m) == target) {
                return m;
            }

            if (query(m) > target)  {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return -1;
    } 

};

void solve() {
    int n, m, q; re(n, m, q);
    vt <int> v(n); re(v);
    vt <vt <pair <int, int>>> queries(n);
    for (int i = 0; i < q; ++i) {
        int a, b; re(a, b);
        --a, --b;
        queries[a].emb(b, i);
    }

    BIT T(n + 1);
    vt <ll> ansq(q);
    vt <int> last_vis(n, -1);
    for (int i = n - 1; i >= 0; --i) {
        if (last_vis[v[i]] != -1)
            T.upd(last_vis[v[i]] + 1, -v[i]);

        T.upd(i + 1, v[i]);
        last_vis[v[i]] = i;

        for (auto& it : queries[i]) {
            ansq[it.second] = T.query(i + 1, it.first + 1);
        }
    }

    for (int i = 0; i < q; ++i)
        wr(ansq[i], '\n');
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("distincte");

    int t = 1;
    for(;t;t--) {
        solve();
    }
    
    return 0;
}