#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define lll __int128_t
#define ulll __uint128_t
#define ld long double
#define lld __float128
#define fi first
#define se second
#define mp make_pair
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U>
bool chmax(T &x, U v) {return (v > x)? x=v,1 : 0;}
template<typename T, typename U>
bool chmin(T &x, U v) {return (v < x)? x=v,1 : 0;}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #define DEBUG
#ifdef DEBUG
#define _main "\e[36m"
#define _reset "\e[39m\n"
template<typename T>
inline void __print(T x) {cerr << x;}
template<typename T, typename U>
inline void __print(pair<T,U> x)
{
cerr << "("; __print(x.fi); cerr << ", "; __print(x.se); cerr << ")";
}
inline void _print() {}
template<typename T, typename... U>
inline void _print(T x, U... y)
{
__print(x);
if(sizeof...(y)) cerr << ", ";
_print(y...);
}
template<typename T>
inline void _print_arr(T x) {__print(x);}
template<typename T, typename... U>
inline void _print_arr(T x, int size, U... len)
{
cerr << "[";
bool has = sizeof...(len);
for(int i = 0; i < size; i++)
{
if(i) cerr << "," << (has? "\n" : " ");
_print_arr(x[i], len...);
}
cerr << "]";
}
#define _source source_location::current()
#define debug_pref(a) cerr << _main << _source.file_name() << ":" << _source.line() << ":" << _source.column() << " [" << a << "]";
#define debug(a...) {debug_pref(#a); cerr << " = ["; _print(a); cerr << "]" << _reset;}
#define debug_arr(a, sz...) {debug_pref(#a); cerr << " = "; _print_arr(a, sz); cerr << _reset;}
#endif
#ifndef DEBUG
#define debug(a...)
#define debug_arr(a, sz...)
#endif
/*
permute both arrays with the same permutation such that second array is sorted
now look at the first array
if i have value x and position i, it will add 1 to answer if segment [L, L+K-1] covers x
so if i=x, we add 1 for all start poses [i-K+1, i]
if i<x, we add 1 for [x-K+1, i] (if x-K+1 <= i of course)
if i>x, we add 1 for [i-K+1, x]
so we can find maximum+count on a segment 0...n-k+1 easily.
updates are easy, remove both values, then add them back in a different order
this was a bit incorrect, because we care about BOTH segments. This means each pair [i, x]
is rectangle, not a segment. And we try to find biggest intersection.
does 2d segtree work? if its implicit, then i guess it does
*/
const int MAXN = 100005;
const int MLOG = 18;
const int MAXC = MAXN*3 * MLOG;
struct dat
{
int max;
int cnt;
dat(int val) : max(val), cnt(1) {}
dat() : max(0), cnt(0) {}
dat(int max, int cnt) : max(max), cnt(cnt) {}
};
inline dat comb(dat a, dat b)
{
if(a.max > b.max) return a;
if(a.max < b.max) return b;
return dat(a.max, a.cnt + b.cnt);
}
struct segtree
{
struct node
{
dat dt;
int add;
int l, r;
node() : dt(), add(0), l(0), r(0) {}
};
vector<node> tre;
int n;
int ctr, root;
segtree() {}
segtree(int n, int cap)
{
this->n = n;
tre = vector<node>(cap);
ctr = 1;
root = 0;
}
inline int nw(int l, int r)
{
int v = ctr++;
tre[v] = node();
tre[v].dt = dat(0, r-l+1);
return v;
}
inline int _add_node(int v, int l, int r, int x)
{
if(!v)
v = nw(l, r);
tre[v].dt.max += x;
tre[v].add += x;
return v;
}
inline void push(int v, int l, int r)
{
if(!v)
return;
if(!tre[v].add)
return;
if(l == r)
return;
int m = (l+r) / 2;
tre[v].l = _add_node(tre[v].l, l, m, tre[v].add);
tre[v].r = _add_node(tre[v].r, m+1, r, tre[v].add);
tre[v].add = 0;
}
inline int _add(int l, int r, int L, int R, int v, int x)
{
if(!v)
v = nw(l, r);
push(v, l, r);
if(l >= L && r <= R)
{
_add_node(v, l, r, x);
return v;
}
if(l > R || r < L)
return v;
int m = (l+r) / 2;
tre[v].l = _add(l, m, L, R, tre[v].l, x);
tre[v].r = _add(m+1, r, L, R, tre[v].r, x);
tre[v].dt = comb(tre[tre[v].l].dt, tre[tre[v].r].dt);
return v;
}
inline dat _get(int l, int r, int L, int R, int v)
{
if(!v)
return dat();
push(v, l, r);
if(l >= L && r <= R)
return tre[v].dt;
if(l > R || r < L)
return dat();
int m = (l+r) / 2;
return comb(
_get(l, m, L, R, tre[v].l),
_get(m+1, r, L, R, tre[v].r)
);
}
// public
inline void add(int l, int r, int x)
{
chmax(l, 0);
chmin(r, n-1);
root = _add(0, n-1, l, r, root, x);
}
inline dat get(int l, int r)
{
return _get(0, n-1, l, r, root);
}
};
struct kinda_tree
{
vector<dat> tre;
int n;
kinda_tree(int n)
{
this->n = n;
tre = vector<dat>(n*4, dat());
}
inline void _set(int l, int r, int v, int i, dat dt)
{
if(l == r)
{
tre[v] = dt;
return;
}
int m = (l+r) / 2;
if(i <= m)
_set(l, m, v*2, i, dt);
else
_set(m+1, r, v*2+1, i, dt);
tre[v] = comb(tre[v*2], tre[v*2+1]);
}
// public
inline void set(int i, dat dt)
{
_set(0, n-1, 1, i, dt);
}
inline dat get()
{
return tre[1];
}
};
int main()
{
fast;
int n, k, q; cin >> n >> k >> q;
int p1[n];
for(int i = 0; i < n; i++)
{
cin >> p1[i]; p1[i]--;
}
int p2[n];
for(int i = 0; i < n; i++)
{
cin >> p2[i]; p2[i]--;
}
int dat[n];
int pos[n];
for(int i = 0; i < n; i++)
{
dat[i] = p1[i];
pos[p2[i]] = i;
}
segtree st[n];
for(int i = 0; i < n; i++) {
st[i] = segtree(n, MAXC);
}
kinda_tree kt(n);
for(int i = 0; i < n; i++)
{
for(int x = max(0, i-k+1); x <= i; x++)
{
st[x].add(pos[dat[i]]-k+1, pos[dat[i]], 1);
}
}
for(int i = 0; i <= n-k; i++)
{
kt.set(i, st[i].get(0, n-k));
}
for(int i = 0; i <= q; i++)
{
if(i)
{
int x; cin >> x; x--;
// debug(x-k+1, x+1, pos[dat[x]]-k+1, pos[dat[x]], dat[x+1]-k+1, dat[x+1]);
// move dat[x] to x+1
if(x-k+1 >= 0)
st[x-k+1].add(pos[dat[x]]-k+1, pos[dat[x]], -1);
st[x+1].add(pos[dat[x]]-k+1, pos[dat[x]], 1);
// move dat[x+1] to x
st[x+1].add(pos[dat[x+1]]-k+1, pos[dat[x+1]], -1);
if(x-k+1 >= 0)
st[x-k+1].add(pos[dat[x+1]]-k+1, pos[dat[x+1]], 1);
swap(dat[x], dat[x+1]);
// update kinda_tree
if(x-k+1 >= 0)
kt.set(x-k+1, st[x-k+1].get(0, n-k));
if(x+1 <= n-k)
kt.set(x+1, st[x+1].get(0, n-k));
}
auto res = kt.get();
cout << res.max << ' ' << res.cnt << '\n';
}
}
/*
2 1 1
1 2
1 2
1
2 1 0
1 2
1 2
4 3 0
2 4 1 3
1 2 3 4
5 3 3
1 4 3 2 5
4 5 1 2 3
3
1
4
*/
