#include <bits/stdc++.h>
using namespace std;
const int nx=5e5+5;
int n, k, q, T, tmp, x, y, u, v, cnt;
struct tree
{
int rt, rtg, p[nx], t, in[nx], out[nx], sz[nx], hd[nx], lvl[nx], on[nx], dist[nx];
vector<tuple<int, int, int, int, int>> qrs;
vector<int> d[nx];
vector<pair<int, int>> g[nx];
void init()
{
for (int i=1; i<=n; i++)
{
cin>>p[i];
if (p[i]==-1) rt=i;
else d[p[i]].push_back(i);
}
dfs(rt);
hld(rt, rt);
vector<pair<int, int>> srt;
for (int i=1; i<=k; i++) on[i]=1, srt.push_back({in[i], i});
sort(srt.begin(), srt.end());
for (int i=1; i<k; i++) on[lca(srt[i-1].second, srt[i].second)]=1;
srt.clear();
for (int i=1; i<=n; i++) if (on[i]) srt.push_back({in[i], i});
sort(srt.begin(), srt.end());
stack<int> s;
for (auto [_, u]:srt)
{
if (!rtg)
{
rtg=u;
s.push(u);
continue;
}
//cout<<"u "<<u<<endl;
while (!(in[s.top()]<=in[u]&&out[u]<=out[s.top()])) s.pop();
g[s.top()].push_back({u, 0});
s.push(u);
}
dfs2(rtg);
}
void init2()
{
dfsg(rtg);
}
void dfs(int u)
{
sz[u]=1;
in[u]=++t;
for (auto v:d[u]) lvl[v]=lvl[u]+1, dfs(v), sz[u]+=sz[v];
out[u]=t;
}
void dfs2(int u)
{
for (auto [v, w]:g[u]) dfs2(v);
for (int i=0; i<g[u].size(); i+=2)
{
if (i==g[u].size()-1) qrs.push_back({u, g[u][i].first, u, i, 0});
else qrs.push_back({g[u][i].first, g[u][i+1].first, u, i, 1});
}
}
void dfsg(int u)
{
for (auto [v, w]:g[u]) dist[v]=dist[u]+w, dfsg(v);
}
void hld(int u, int h)
{
hd[u]=h;
pair<int, int> hv;
for (auto v:d[u]) hv=max(hv, {sz[v], v});
if (hv.second) hld(hv.second, h);
for (auto v:d[u]) if (v!=hv.second) hld(v, v);
}
int lca(int u, int v)
{
while (hd[u]!=hd[v])
{
if (lvl[hd[u]]>lvl[hd[v]]) swap(u, v);
v=p[hd[v]];
}
if (lvl[u]>lvl[v]) swap(u, v);
return u;
}
int query(int u, int v)
{
return dist[u]-dist[lca(u, v)]+dist[v]-dist[lca(u, v)];
}
} t1, t2;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>k>>q>>T;
t1.init();
t2.init();
for (int i=1; i<=k; i++) cout<<i<<' ';
cout<<endl;
for (auto [u, v, _a, _b, _c]:t1.qrs) cout<<"? "<<u<<' '<<v<<'\n';
for (auto [u, v, _a, _b, _c]:t2.qrs) cout<<"? "<<u<<' '<<v<<'\n';
cout<<"!"<<endl;
for (auto [_a, _b, u, i, t]:t1.qrs)
{
cin>>x>>y>>tmp>>tmp;
if (!t) t1.g[u][i].second=y;
else t1.g[u][i].second=x, t1.g[u][i+1].second=y;
}
for (auto [_a, _b, u, i, t]:t2.qrs)
{
cin>>tmp>>tmp>>x>>y;
if (!t) t2.g[u][i].second=y;
else t2.g[u][i].second=x, t2.g[u][i+1].second=y;
}
t1.init2();
t2.init2();
while (T--)
{
cin>>u>>v;
cout<<t1.query(u, v)<<' '<<t2.query(u, v)<<'\n';
}
cout<<endl;
}
