#include <vector>
#include <fstream>
#include <set>
#include <map>
int main(){
    std::vector<long> v;
    long n,k,m;
    std::ifstream in("distincte.in");
    std::ofstream out("distincte.out");
    in>>n>>k>>m;
    for (long i=0;i<n;i++) {
        long t;
        in>>t;
        v.push_back(t);
        }
    std::map<long,long> mi;
    std::map<long,long>::iterator mit;
    typedef std::pair<int,int> pz;
    for (long i=0;i<m;i++){
        long a,b;
        in>>a>>b;
        mi.insert(pz(a,b));
        }
        std::set<long> sm;
        std::set<long>::const_iterator smi;
    for (mit=mi.begin();mit!=mi.end();++mit){
         for(long x=mit->first;x<=mit->second;++x) sm.insert(toupper(v[x]));
         int s=0;
         for(smi=sm.begin();smi!=sm.end();++smi) s+=*smi;
         sm.clear();
         out<<s%666013<<"\n";
        }
        return 0;
        }