#include<stdio.h>    
#define M 666013  
long a[265150],st[265150],dr[265150],n,m,y,z,zero=1,fs,fd,tata,k;         
long query(long p);         
int main()         
{         
    long i;         
    freopen("distincte.in","r",stdin);         
    freopen("distincte.out","w",stdout);         
    scanf("%ld %ld %ld",&n,&k,&m);         
    while(zero<n)         
        zero<<=1;         
    zero--;         
    for(i=zero+1;i<=zero+n;++i){         
        st[i]=i-zero;         
        dr[i]=i-zero;         
        scanf("%ld",&a[i]);         
    }         
    for(i=n+1;i<=zero+1;++i){         
        st[zero+i]=i;         
        dr[zero+i]=i;         
    }         
    for(i=zero;i>=1;--i){         
        fs=i<<1;         
        fd=fs|1;         
        st[i]=st[fs];         
        dr[i]=dr[fd];         
        a[i]=a[fs]+a[fd];         
    }         
    for(;m;m--)
        scanf("%ld %ld",&y,&z);         
            printf("%ld\n",query(1)%M);             
    fcloseall();         
    return 0;         
}         
long query(long p)         
{         
    long m1,m2;         
    if(y>dr[p])         
        return 0;         
    if(z<st[p])         
        return 0;         
    if(y<=st[p] && z>=dr[p])         
        return a[p]%M;         
    m1=query(p<<1)%M;         
    m2=query((p<<1)|1)%M;         
    m1=(m1+m2)%M;         
    return m1%M;  
}