#include <stdio.h>
#define modul 666013
int v[100001], last[100001], before[100001], n, m, k, used[100001], sum;

int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    int i, j, a, b;    
    scanf("%d%d%d", &n, &k, &m);
    
    for(i = 1; i <= n; ++i)
    {
          scanf("%d", &v[i]);
          before[i] = last[v[i]];
          last[v[i]] = i;
    }
    
    for(i = 1; i <= m; ++i)
    {
          sum = 0;
          scanf("%d%d", &a, &b);
          for(j = b; j >= a; --j)
          {
                if(!used[j])
                {
                      sum += v[j];
                      sum %= modul;
                }
                if(before[j] >= a)
                        used[before[j]] = 1;
          }
          for(j = b; j >= a; --j)
                used[j] = 0;
                
          printf("%d\n", sum);
    }
    
    return 0;
}