program distincte;
const
  fin='distincte.in';
  fout='distincte.out';
type
  list=^elem;
  elem=record
    urm:list;x:longint;
    end;
  arb=^nod;
  nod=record
    cap:list;
    st,dr:longint;
    end;
var
  a:array[1..200000-1] of arb;
  sir:array[1..100000] of longint;
  p,q:list;
  f,g:list;
  i,j,k,n,m,x,y,s:longint;

procedure interclaseaza(var a,b,c:list);
  var
    m,p,q,aux:list;
  begin
    m:=a;
    p:=b^.urm;
    q:=c^.urm;
    while (p<>nil)and(q<>nil) do
      begin
        if p^.x<q^.x then
          begin
            new(aux);
            aux^.x:=p^.x;
            m^.urm:=aux;
            aux^.urm:=nil;
            m:=aux;
            p:=p^.urm;
          end
        else if q^.x<p^.x then
          begin
            new(aux);
            aux^.x:=q^.x;
            m^.urm:=aux;
            aux^.urm:=nil;
            m:=aux;
            q:=q^.urm;
          end
        else
          begin
            new(aux);
            aux^.x:=p^.x;
            m^.urm:=aux;
            aux^.urm:=nil;
            m:=aux;
            p:=p^.urm;
            q:=q^.urm;
          end;
      end;
    while p<>nil do
      begin
        new(aux);
        aux^.x:=p^.x;
        m^.urm:=aux;
        aux^.urm:=nil;
        m:=aux;
        p:=p^.urm;
      end;
    while q<>nil do
      begin
        new(aux);
        aux^.x:=q^.x;
        m^.urm:=aux;
        aux^.urm:=nil;
        m:=aux;
        q:=q^.urm;
      end;
  end;

procedure build(index,st,dr:longint);
  var
    mid:longint;
  begin
    if st=dr then
      begin
        new(a[index]);
        a[index]^.st:=st;a[index]^.dr:=dr;
        new(a[index]^.cap);
        new(p);
        a[index]^.cap^.urm:=p;
        p^.urm:=nil;
        p^.x:=sir[st];
      end
    else
      begin
        new(a[index]);
        a[index]^.st:=st;a[index]^.dr:=dr;
        new(a[index]^.cap);
        a[index]^.cap^.urm:=nil;
        mid:=(st+dr)shr 1;
        build(index shl 1,st,mid);
        build(index shl 1 or 1,mid+1,dr);
        interclaseaza(a[index]^.cap,a[index shl 1]^.cap,a[index shl 1 or 1]^.cap);
      end;
  end;

procedure query(index,st,dr:longint);
  var
    mid:longint;
  begin
    if (x<=st)and(dr<=y) then
      begin
        interclaseaza(g,f,a[index]^.cap);
        f:=g;
      end
    else
      begin
        mid:=(st+dr)shr 1;
        if x<=mid then
          query(index shl 1,st,mid);
        if y>mid then
          query(index shl 1 or 1,mid+1,dr);
      end;
  end;

begin
  assign(input,fin);
    reset(input);
    readln(n,k,m);
    for i:=1 to n do
      readln(sir[i]);
    build(1,1,n);
  assign(output,fout);
    rewrite(output);
    for i:=1 to m do
      begin
        readln(x,y);
        new(f);new(g);g^.urm:=nil;
        f^.urm:=nil;
        query(1,1,n);
        s:=0;
        g:=f^.urm;
        while g<>nil do
          begin
            s:=(s+g^.x)mod 666013;
            g:=g^.urm;
          end;
        writeln(s);
      end;
  close(output);
  close(input);
end.