#include <cstdio>
 
const int MAX_SIZE(100001);
const int MOD(666013);
 
int numbers [MAX_SIZE];
int next_index [MAX_SIZE];
int bit [MAX_SIZE];
int solution [MAX_SIZE];
 
int heap_size;
 
struct query
{
    int index;
    int left;
    int right;
} heap [MAX_SIZE];
 
inline bool operator > (struct query a, struct query b)
{
    if (a.left > b.left)
        return true;
    return false;
}
 
inline void operator ^= (struct query &a, struct query &b)
{
    a.index ^= b.index;
    a.left ^= b.left;
    a.right ^= b.right;
}
 
inline void swap (int a, int b)
{
    heap[a] ^= heap[b];
    heap[b] ^= heap[a];
    heap[a] ^= heap[b];
}
 
inline void heap_up (void)
{
    if (heap_size == 1)
        return;
    int index(heap_size), father(index >> 1);
    struct query value(heap[index]);
    while (true)
    {
        if (value > heap[father])
            heap[index] = heap[father];
        else
            break;
        index = father;
        if (father > 1)
            father >>= 1;
        else
            break;
    }
    heap[index] = value;
}
 
inline void heap_down (void)
{
    int index(1), left(2), right(3), greatest;
    while (true)
    {
        if (left <= heap_size && heap[left] > heap[index])
            greatest = left;
        else
            greatest = index;
        if (right <= heap_size && heap[right] > heap[greatest])
            greatest = right;
        if (greatest == index)
            break;
        swap(index,greatest);
        index = greatest;
        left = index << 1;
        right = left + 1;
    }
}
 
inline void push (int index, int left, int right)
{
    ++heap_size;
    heap[heap_size].index = index;
    heap[heap_size].left = left;
    heap[heap_size].right = right;
    heap_up();
}
 
inline void pop (void)
{
    heap[1] = heap[heap_size];
    --heap_size;
    heap_down();
}
 
inline int lsb (int x)
{
    return x & -x;
}
 
inline void bit_unique_update (const int value, int index, const int size)
{
    const int position(index);
    while (index <= size)
    {
        bit[index] += value;
        if (bit[index] >= MOD)
            bit[index] -= MOD;
        index += lsb(index);
    }
    index = next_index[value];
    if (index)
        while (index <= size)
        {
            bit[index] -= value;
            if (bit[index] < 0)
                bit[index] += MOD;
            index += lsb(index);
        }
    next_index[value] = position;
}
 
inline int bit_query (int index)
{
    int sum(0);
    while (index)
    {
        sum += bit[index];
        if (sum >= MOD)
            sum -= MOD;
        index -= lsb(index);
    }
    return sum;
}
 
int main (void)
{
    std::freopen("distincte.in","r",stdin);
    std::freopen("distincte.out","w",stdout);
    int n, k, m;
    std::scanf("%d%d%d",&n,&k,&m);
    int *iterator, *end;
    for (iterator = numbers + 1, end = numbers + n ; iterator <= end ; ++iterator)
        std::scanf("%d",iterator);
    int index, left, right, *left_ptr(&left), *right_ptr(&right);
    for (index = 0 ; index < m ; ++index)
    {
        std::scanf("%d%d",left_ptr,right_ptr);
        push(index,left,right);
    }
    std::fclose(stdin);
    index = n;
    while (heap_size)
    {
        left = heap[1].left;
        right = heap[1].right;
        while (index && index >= left)
        {
            bit_unique_update(numbers[index],index,n);
            --index;
        }
        solution[heap[1].index] = bit_query(right);
        pop();
    }
    for (iterator = solution, end = solution + m ; iterator < end ; ++iterator)
        std::printf("%d\n",*iterator);
    std::fclose(stdout);
    return 0;
}