#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
int p[3][500005];
int h[3][500005];
int pathsum[500005];
int up[19][500005];
vector<int> nodes[3][500005];
bool marked[500005];
queue<int> q;
struct ceva
{
int unu;
int doi;
int trei;
int patru;
};
ceva query(int a, int b)
{
int unu,doi,trei,patru;
cout << "? " << a << " " << b << endl;
cin >> unu >> doi >> trei >> patru;
return {unu,doi,trei,patru};
}
void dfs(int node, int parent)
{
for (auto x : nodes[1][node])
{
if (marked[x])
{
h[1][x]=h[1][node]+1;
pathsum[x]=pathsum[node]+query(x,node).unu;
dfs(x,node);
}
}
}
int lca(int a, int b)
{
if (h[1][a]<h[1][b])
swap(a,b);
int k,i;
k=h[1][a]-h[1][b];
for (i=18; i>=0; i--)
{
if (k&(1<<i))
a=up[i][a];
}
if (a==b)
return a;
for (i=18; i>=0; i--)
{
if (up[i][a]!=up[i][b])
{
a=up[i][a];
b=up[i][b];
}
}
return up[0][a];
}
int dist(int a, int b)
{
int c;
c=lca(a,b);
return pathsum[a]+pathsum[b]-2*pathsum[c];
}
signed main()
{
/*
ifstream fin("arbore.in");
ofstream fout("arbore.out");
*/
///ios_base::sync_with_stdio(0);
///cin.tie(0);
///cout.tie(0);
int n,k,qq,t,i,root,a,b,fr,j;
cin >> n >> k >> qq >> t;
for (i=1; i<=n; i++)
{
cin >> p[1][i];
if (p[1][i]==-1)
root=i;
else
nodes[1][p[1][i]].push_back(i);
}
for (i=1; i<=n; i++)
{
cin >> p[2][i];
if (p[2][i]!=-1)
nodes[2][p[2][i]].push_back(i);
}
///sub1
q.push(root);
while (k>0)
{
fr=q.front();
debug(fr);
marked[fr]=1;
for (auto x : nodes[1][fr])
{
q.push(x);
}
k--;
q.pop();
}
for (i=1; i<=n; i++)
{
if (marked[i])
cout << i << " ";
}
cout << endl;
pathsum[root]=0;
h[1][root]=1;
dfs(root,-1);
cout << "!" << endl;
for (i=1; i<=n; i++)
{
up[0][i]=p[1][i];
}
for (i=1; i<=18; i++)
{
for (j=1; j<=n; j++)
{
up[i][j]=up[i-1][up[i-1][j]];
}
}
for (i=1; i<=t; i++)
{
cin >> a >> b;
cout << dist(a,b) << " " << dist(a,b) << endl;
}
cout << endl;
return 0;
}
