#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define pb push_back
#define f first
#define s second
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iii tuple<int,int,int>
#define eb emplace_back
int n,k,q;
using pll = pair<int,int>; // (maxValue, count)
// combine: pick larger max; if tie, add counts
static inline pll combine(pll a, pll b){
if(a.first == b.first) return {a.first, a.second + b.second};
return (a.first > b.first ? a : b);
}
struct Node {
int s, e, m;
int lz;
pll v;
Node *l, *r;
Node(int S, int E): s(S), e(E), lz(0), l(nullptr), r(nullptr) {
m = (s + e) / 2;
v = {0, e - s + 1}; // all zeros => max=0, count=segment length
}
} *roots[100005];
// clone exactly once
static inline Node* clone(Node* t){
Node* c = new Node(t->s, t->e);
c->m = t->m;
c->lz = t->lz;
c->v = t->v;
c->l = t->l;
c->r = t->r;
return c;
}
// apply lazy add to whole node (no pushing)
static inline void apply(Node* t, int add){
t->v.first += add;
t->lz += add;
}
// Pull up from children; null child means "implicit zeros" with full length
static inline void pull(Node* t){
int leftLen = t->m - t->s + 1;
int rightLen = t->e - t->m;
pll lv = t->l ? t->l->v : pll{0, leftLen};
pll rv = t->r ? t->r->v : pll{0, rightLen};
t->v = combine(lv, rv);
}
// PUSH lazy to children, cloning children at most once (only if lz != 0)
static inline void push(Node* t){
if(t->lz == 0 || t->s == t->e) return;
// ensure left child exists and is unique for this version
if(!t->l) t->l = new Node(t->s, t->m);
else t->l = clone(t->l);
apply(t->l, t->lz);
// ensure right child exists and is unique for this version
if(!t->r) t->r = new Node(t->m + 1, t->e);
else t->r = clone(t->r);
apply(t->r, t->lz);
t->lz = 0;
}
// Range add [L,R] by add, persistent: returns new node pointer
Node* update(Node* t, int L, int R, int add){
if(!t) return nullptr; // shouldn't happen for your root, but safe
Node* res = clone(t);
if(L <= res->s && res->e <= R){
apply(res, add);
return res;
}
push(res);
if(R <= res->m){
if(!res->l) res->l = new Node(res->s, res->m); // create only when needed
res->l = update(res->l, L, R, add);
} else if(L > res->m){
if(!res->r) res->r = new Node(res->m + 1, res->e);
res->r = update(res->r, L, R, add);
} else {
if(!res->l) res->l = new Node(res->s, res->m);
if(!res->r) res->r = new Node(res->m + 1, res->e);
res->l = update(res->l, L, res->m, add);
res->r = update(res->r, res->m + 1, R, add);
}
pull(res);
return res;
}
/*const pll sen={0, 0};
struct Node {
pll v;
int s,e,m,lz;
Node *l, *r;
Node (int S,int E){
s=S; e=E;
if(s+e>=0) m=(s+e)/2;
else m=(s+e-1)/2;
v={0ll,e-s+1};
lz=0;
l=r=nullptr;
}
void prop(){
if(lz==0 or (s==e))return;
if(!l)l=new Node(s, m);
else l=dupe(l);
l->v.f+=lz;
l->lz+=lz;
if(!r)r=new Node(m+1, e);
else r=dupe(r);
r->v.f+=lz;
r->lz+=lz;
lz=0;
}
Node* dupe(Node *node){
Node* ret=new Node(node->s,node->e);
ret->v=node->v;
ret->l=node->l; ret->r=node->r;
ret->lz=node->lz;
return ret;
}
} * roots[100005];
Node* dupe(Node *node){
Node* ret=new Node(node->s,node->e);
ret->v=node->v;
ret->l=node->l; ret->r=node->r;
ret->lz=node->lz;
return ret;
}
pll combine(pll a, pll b){
if(a.f == b.f) return mp(a.f, a.s + b.s);
else return max(a, b);
}
void update(Node * node, int S, int E, int V){ // pass pointer *
int & s=node->s, & m=node->m, &e=node->e, &lz=node->lz;
pll &v=node->v;
Node* &l=node->l;
Node* &r= node->r;
if((s==S and e==E) or (s==e)){
v.f += V;
lz+=V;
//printf("SEGMENT %d to %d, v.f %d, v.s %d\n",s,e,v.f, v.s);
return;
}
node->prop();
if(E<=m){
if(!l) l=new Node(s,m);
else l=dupe(l);
update(l, S,E,V);
}
else if(S > m){
if(!r) r=new Node(m+1,e);
else r=dupe(r);
update(r,S,E,V);
}
else {
if(!l) l=new Node(s,m);
else l=dupe(l);
update(l, S,m,V);
if(!r) r=new Node(m+1,e);
else r=dupe(r);
update(r, m+1,E,V);
}
v=combine((l?l->v:mp(0, m-s+1)), (r?r->v:mp(0, e-m)));
//printf("SEGMENT %d to %d, v.f %d, v.s %d\n",s,e,v.f, v.s);
}*/
signed main(){
cin>>n>>k>>q;
vector<int> a(n+1,0), b(n+1, 0);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
int c;cin>>c;
b[c]=i;
}
for(int i=1;i<=n;i++){
a[i]=b[a[i]];
//printf("a[%d] is %d\n", i, a[i]);
}
map<int,int> mappa;
roots[k]=new Node(1, n);
for(int i=1;i<=k;i++){
//for (int j=a[i];j<=min(n, a[i]+k-1);j++) update(roots[k], j, j, 1);
//if(a[i] <= n-k+1)
roots[k]=update(roots[k], max(k, a[i]), min(n,a[i]+k-1), 1);
}
mappa[roots[k]->v.f] += roots[k]->v.s;
//printf("%lld, %lld\n",roots[k]->v.f, roots[k]->v.s);
for(int i=k+1;i<=n;i++){
//for (int j=a[i-k];j<=min(n, a[i-k]+k-1);j++) update(roots[i], j, j, -1);
//if (a[i-k] <= n-k+1)
roots[i]=update(roots[i-1], max(k,a[i-k]), min(n,a[i-k]+k-1), -1);
//for (int j=a[i];j<=min(n, a[i]+k-1);j++) update(roots[i], j, j, 1);
//if (a[i] <= n-k+1)
roots[i]=update(roots[i], max(k,a[i]), min(n, a[i]+k-1), 1);
mappa[roots[i]->v.f] += roots[i]->v.s;
}
auto [l, c] = *(prev(mappa.end()));
cout<<l<<" "<<c<<'\n';
while(q--){
int a,b;cin>>a>>b;
cout<<l<<" "<<c<<'\n';
}
}
