#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 CAP = MLOG * 2 * 3 * MAXN;
struct dat
{
int sum, max, cnt;
dat() : sum(0), max(-1e9), cnt(0) {}
dat(int size) : sum(0), max(0), cnt(size) {}
};
inline dat cmb(dat a, dat b)
{
dat c;
c.sum = a.sum + b.sum;
int maxr = a.sum + b.max;
int cntr = b.cnt;
int maxl = a.max;
int cntl = a.cnt;
if(maxr > maxl) {
c.max = maxr;
c.cnt = cntr;
} else if(maxr < maxl) {
c.max = maxl;
c.cnt = cntl;
} else {
c.max = maxl;
c.cnt = cntl+cntr;
}
return c;
}
struct node
{
int l, r;
dat dt;
node() : l(0), r(0), dt(dat()) {}
node(int size) : l(0), r(0), dt(dat(size)) {}
};
node tre[CAP];
int ctr;
struct segtree
{
inline void upd(int v, int l, int r)
{
if(!v)
return;
int m = (l+r) / 2;
auto dtl = tre[v].l ? tre[tre[v].l].dt : dat(m-l+1);
auto dtr = tre[v].r ? tre[tre[v].r].dt : dat(r-m);
tre[v].dt = cmb(dtl, dtr);
}
inline int nw(int size)
{
int v = ctr++;
if(v >= CAP)
{
assert(0);
}
tre[v] = node(size);
return v;
}
inline int cp(int v)
{
int u = nw(0);
tre[u].l = tre[v].l;
tre[u].r = tre[v].r;
tre[u].dt = tre[v].dt;
return u;
}
int n;
vector<int> roots;
segtree(int n)
{
this->n = n;
roots = vector<int>(n, 0);
ctr = 1;
}
inline int _add(int l, int r, int v, int i, int x)
{
v = v ? cp(v) : nw(r-l+1);
if(l == r)
{
tre[v].dt.max += x;
tre[v].dt.sum += x;
return v;
}
int m = (l+r) / 2;
if(i <= m)
tre[v].l = _add(l, m, tre[v].l, i, x);
else
tre[v].r = _add(m+1, r, tre[v].r, i, x);
upd(v, l, r);
return v;
}
inline dat _get(int l, int r, int L, int R, int v)
{
if(!v)
return dat();
if(l >= L && r <= R)
return tre[v].dt;
if(l > R || r < L)
return dat();
int m = (l+r) / 2;
return cmb(
_get(l, m, L, R, tre[v].l),
_get(m+1, r, L, R, tre[v].r)
);
}
// public
inline void copy(int i, int j)
{
debug("copy", i, j);
roots[j] = roots[i];
}
inline void add(int i, int j, int x)
{
if(j < 0 || j >= n)
return;
roots[i] = _add(0, n-1, roots[i], j, x);
}
inline void add(int i, int l, int r, int x)
{
chmax(l, 0);
chmin(r, n-1);
if(l > r)
return;
debug("add", i, l, r, x);
add(i, l, x);
add(i, r+1, -x);
}
inline dat get(int i, int l, int r)
{
return _get(0, n-1, l, r, roots[i]);
}
};
struct kinda_tree
{
struct dat2
{
ll max, cnt;
dat2() : max(-1e9), cnt(0) {}
dat2(dat &dt) : max(dt.max), cnt(dt.cnt) {}
};
inline dat2 cmb(dat2 a, dat2 b)
{
dat2 c;
if(a.max > b.max)
return a;
if(a.max < b.max)
return b;
c.max = a.max;
c.cnt = a.cnt + b.cnt;
return c;
}
vector<dat2> tre;
int n;
kinda_tree(int n)
{
this->n = n;
tre = vector<dat2>(n*4, dat2());
}
inline void _set(int l, int r, int v, int i, dat2 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] = cmb(tre[v*2], tre[v*2+1]);
}
// public
inline void set(int i, dat dt)
{
_set(0, n-1, 1, i, dat2(dt));
}
inline dat2 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);
kinda_tree kt(n);
for(int i = n-1; i >= 0; i--)
{
st.add(i, pos[dat[i]]-k+1, pos[dat[i]], 1);
if(i+k < n)
st.add(i, pos[dat[i+k]]-k+1, pos[dat[i+k]], -1);
if(i > 0)
st.copy(i, i-1);
}
for(int i = 0; i <= n-k; i++)
{
kt.set(i, st.get(i, 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.add(x-k+1, pos[dat[x]]-k+1, pos[dat[x]], -1);
if(x+1 <= n-k)
st.add(x+1, pos[dat[x]]-k+1, pos[dat[x]], 1);
// move dat[x+1] to x
if(x+1 <= n-k)
st.add(x+1, pos[dat[x+1]]-k+1, pos[dat[x+1]], -1);
if(x-k+1 >= 0)
st.add(x-k+1, 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.get(x-k+1, 0, n-k));
if(x+1 <= n-k)
kt.set(x+1, st.get(x+1, 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
*/
