#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
vector<vector<int>> G1, G2;
int N, K, Q, T, r1, r2;
int dep1[1000009], dep2[1000009], par1[30][1000009], par2[30][1000009];
vector<int> sorted;
class UnionFind {
public:
vector<int> par, siz, dist;
void init(int n) {
par.assign(n + 1, -1); siz.assign(n + 1, 1); dist.assign(n + 1, 0);
}
int root(int x) {
if (par[x] == -1) return x;
int r = root(par[x]);
dist[x] += dist[par[x]];
return par[x] = r;
}
int distance(int u, int v) {
int ru = root(u), rv = root(v);
if (ru != rv) return 1e9;
return dist[v] - dist[u];
}
bool unite(int u, int v, int d) {
int ru = root(u), rv = root(v);
if (ru == rv) {
//assert(dist(u, v) == d);
return 0;
}
d += dist[u]; d -= dist[v];
if (siz[ru] > siz[rv]) {
swap(ru, rv); d = -d;
}
siz[rv] += siz[ru];
par[ru] = rv; dist[ru] = -d; return 1;
}
};
void dfs1(int now) {
sorted.push_back(now);
for (int nex : G1[now]) {
dep1[nex] = dep1[now] + 1; par1[0][nex] = now; dfs1(nex);
}
}
void dfs2(int now) {
for (int nex : G2[now]) {
dep2[nex] = dep2[now] + 1; par2[0][nex] = now; dfs2(nex);
}
}
int prevs1(int pos, int d) {
rep(i, 30) if ((d >> i) & 1) pos = par1[i][pos];
return pos;
}
int prevs2(int pos, int d) {
rep(i, 30) if ((d >> i) & 1) pos = par2[i][pos];
return pos;
}
int lca1(int u, int v) {
if (dep1[u] > dep1[v]) swap(u, v);
v = prevs1(v, dep1[v] - dep1[u]);
if (u == v) return u;
for (int i = 29; i >= 0; i--) {
if (par1[i][u] != par1[i][v]) {
u = par1[i][u]; v = par1[i][v];
}
}
return par1[0][u];
}
int lca2(int u, int v) {
if (dep2[u] > dep2[v]) swap(u, v);
v = prevs2(v, dep2[v] - dep2[u]);
if (u == v) return u;
for (int i = 29; i >= 0; i--) {
if (par2[i][u] != par2[i][v]) {
u = par2[i][u]; v = par2[i][v];
}
}
return par2[0][u];
}
int main() {
cin >> N >> K >> Q >> T;
G1.resize(N+1); G2.resize(N+1);
rep1(i, N) {
int p; cin >> p;
if (p == -1) {
r1 = i; dep1[r1] = 0;
}
else G1[p].push_back(i);
}
rep1(i, N) {
int p; cin >> p;
if (p == -1) {
r2 = i; dep2[r2] = 0;
}
else G2[p].push_back(i);
}
dfs1(r1); dfs2(r2);
// ダブリング
rep(i, 29) rep1(j, N) {
par1[i+1][j] = par1[i][par1[i][j]];
par2[i+1][j] = par2[i][par2[i][j]];
}
UnionFind uf1, uf2; uf1.init(N); uf2.init(N);
// 質疑応答
vector<int> subset = sorted;
rep(i, K) {
cout << subset[i];
if (i == K - 1) cout << endl;
else cout << " ";
}
vector<tuple<int, int, int>> q1, q2;
vector<int> col1(N + 1, -1), col2(N + 1, -1);
int curr = subset[0];
while (1) {
col2[curr] = subset[0];
if (curr == r2) break;
curr = par2[0][curr];
}
rep1(i, K-1) {
int cur = subset[i];
while (col2[cur] == -1) {
col2[cur] = subset[i]; cur = par2[0][cur];
}
q2.push_back({col2[cur], subset[i], cur});
cout << "? " << col2[cur] << " " << subset[i] << endl;
}
cout << "!" << endl;
rep(i, K - 1) {
int a, b, c, d; cin >> a >> b >> c >> d;
uf1.unite(lca1(get<0>(q2[i]), get<1>(q2[i])), get<0>(q2[i]), a);
uf1.unite(lca1(get<0>(q2[i]), get<1>(q2[i])), get<1>(q2[i]), b);
uf2.unite(get<2>(q2[i]), get<0>(q2[i]), c);
uf2.unite(get<2>(q2[i]), get<1>(q2[i]), d);
}
vector<int> ans1(T), ans2(T);
rep(i, T) {
int p, q; cin >> p >> q;
ans1[i] = uf1.distance(lca1(p, q), p) + uf1.distance(lca1(p, q), q);
ans2[i] = uf2.distance(lca2(p, q), p) + uf2.distance(lca2(p, q), q);
}
rep(i, T) cout << ans1[i] << " " << ans2[i] << endl;
}
