#include <fstream>
#define modulo 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
int i, aib[100001], n, m, op, number, a, b, sum, k;
void update(int x, int value){
    while(x <= n){
        aib[x] = (aib[x] | number) % modulo;
        x = x + (x & (- x));
    }
}
int quary(int x){
    int s = 0;
    while(x >= 1){
        s = (s + aib[x]) % modulo;
        x = x - (x & (- x));
    }
    return s;
}
int main()
{   f >> n >> k >> m;
    for(i = 1; i <= n; i++){
        f >> number;
        update(i, number);
    }
    for(i = 1; i <= m; i++){
        f >> a >> b;
        sum = quary(b); //- quary(a - 1);
        if(sum < 0)
            sum += modulo;
        g << sum << '\n';
    }
    return 0;
}