#include <bits/stdc++.h>
using namespace std;
ifstream in("distincte1.in");
ofstream out("distincte1.out");
const int nmax=100005,MOD=666013;
pair <int,int> querys[nmax];
int n,k,m,a[nmax];
long long aib[nmax];
int st;
vector <int> valori[nmax];
void update(int p,int x)
{
    for (;p<=n;p+=(p&(-p)))
        aib[p]=aib[p]+x%MOD;
}
int query(int p)
{
    int s=0;
  //  cout<<"a";
    for (;p>0;p-=(p&(-p)))
        s=s+aib[p]%MOD;
    return s%MOD;
}
void advance(int T)
{int i,x;
    for (;st<T;st++)
    {
        x=a[st];
        valori[x][0]++;
         update(st,-x);
        if (valori[x].size()>1)
        {
            update(valori[x][valori[x][0]],x);
        }
    }
}
int main()
{
    in>>n>>k>>m;
    cout<<"a";
    out<<n<<"\n";
    int i,q,w;
    for (i=1;i<=n;i++){in>>a[i];}
    for (i=1;i<=m;i++)
    {
        in>>q>>w;
        querys[i]={q,w};
    }
    sort (querys+1,querys+1+m);
    st=querys[1].first;
    int x;
    for (i=st;i<=n;i++)
    {
        x=a[i];
        if (valori[x].empty()){update(i,x);valori[x].push_back(0);}
        else valori[x].push_back(i);
    }
    for (i=1;i<=n;i++)cout<<query(i)<<" ";
    for (i=1;i<=m;i++)
    {
        if (st<querys[i].first)
        {
            advance(querys[i].first);
        }
       // out<<query(querys[i].second)<<"\n";
    }
    out.close();
    in.close();
    return 0;
}