#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=5e5+;

const ll Base=;

ll n,m,q,cl[N],a[N],b[N];

map<ll,ll> M;

struct Splay{

  ll count2[N],data[N],ls[N],rs[N],fa[N],v[N],vv[N],root=,cnt=;

  void updata(ll x)

  {

    count2[x]=count2[ls[x]]+count2[rs[x]]+;

    data[x]=(data[ls[x]]+1ll*data[rs[x]]*cl[count2[ls[x]]+]

    +cl[count2[ls[x]]]*v[x]);

  }

  void rotate(ll x,ll y)

  {

    ll fa1=fa[x];

    if (y==)

    {

      rs[fa1]=ls[x];

      if (ls[x]) fa[ls[x]]=fa1;

    } else

    {

      ls[fa1]=rs[x];

      if (rs[x]) fa[rs[x]]=fa1;

    }

    fa[x]=fa[fa1];

    if (fa[fa1])

    {

      ls[fa[fa1]]==fa1?ls[fa[fa1]]=x:rs[fa[fa1]]=x;

    }

    fa[fa1]=x;

    if (y==) ls[x]=fa1; else rs[x]=fa1;

    updata(fa1); updata(x);

  }

  void splay(ll x,ll goal)

  {

    ll fa1=fa[x];

    while (fa1!=goal)

    {

      if (fa[fa1]==goal)

        x==ls[fa1]?rotate(x,):rotate(x,);

      else

      if (fa1==ls[fa[fa1]])

        if (x==ls[fa1]) rotate(fa1,),rotate(x,);

          else rotate(x,),rotate(x,);

      else

        if (x==rs[fa1]) rotate(fa1,),rotate(x,);

          else rotate(x,),rotate(x,);

      fa1=fa[x];

    }

    if (!goal) root=x;

  }

  ll search(ll goal)

  {

    ll x=root;

    while (x)

    {

      if (vv[x]==goal) return(x);

      if (vv[x]<goal) x=rs[x];

      else x=ls[x];

    }

  }

  void ins(ll y,ll x1)

  {

    ll x=root;

    while (x)

    {

      if (y>vv[x])

        if (rs[x]) x=rs[x]; else break;

      else

        if (ls[x]) x=ls[x]; else break;

    }

    if (!x) root=++cnt;

    else

    {

      if (y>vv[x])

      {

        rs[x]=++cnt; fa[cnt]=x;

      } else

      {

        ls[x]=++cnt; fa[cnt]=x;

      }

    }

    vv[cnt]=y; v[cnt]=x1; count2[cnt]=;

    splay(cnt,);

  }

  void del(ll x1)

  {

    ll x=search(x1);

    splay(x,);

    if (!ls[x])

    {

      root=rs[root]; fa[root]=; return;

    }

    ll y=ls[x];

    while (rs[y]) y=rs[y];

    rs[y]=rs[x];

    if (rs[y]) fa[rs[y]]=y;

    updata(y);

    root=ls[x]; fa[ls[x]]=; splay(y,);

  }

}A,B;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  ios::sync_with_stdio(false);

  cl[]=;

  for (ll i=;i<N;i++) cl[i]=(1ll*cl[i-]*Base);

  cin>>n>>m>>q;

  ll cnt=;

  for (ll i=;i<m;i++) cnt+=cl[i];

  for (ll i=;i<=n;i++) cin>>a[i];

  for (ll i=;i<=m;i++) A.ins(a[i],i);

  ++M[A.data[A.root]];

  for (ll i=m+;i<=n;i++)

  {

    A.del(a[i-m]); A.ins(a[i],i);

    ll tmp=A.data[A.root]-1ll*cnt*(i-m);

    ++M[tmp];

  }

  for (ll i=;i<=m;i++)

  {

    cin>>b[i];

    B.ins(b[i],i);

  }

  for (ll i=;i<=q;i++)

  {

    ll x,y;

    cin>>x>>y;

    B.del(b[x]);

    b[x]=y;

    B.ins(y,x);

    cout<<M[B.data[B.root]]<<endl;

  }

  return ;

}