#include <bits/stdc++.h>
using namespace std;
struct Tree {
vector<int> tin, tout, par, depth, jump;
int logn;
void init(vector<vector<int>> adj, int root) {
int n = adj.size();
int T = 0;
tin.assign(n, -1), tout.resize(n), par.resize(n), depth.resize(n), jump.resize(n);
par[root] = jump[root] = root;
function<void(int)> dfs = [&](int v) {
tin[v] = T++;
for (int to : adj[v]) {
depth[to] = depth[v] + 1;
par[to] = v;
int p = jump[v];
int pp = jump[p];
if (depth[p] - depth[v] == depth[pp] - depth[p]) {
jump[to] = pp;
} else {
jump[to] = v;
}
dfs(to);
}
tout[v] = T;
};
dfs(root);
logn = __lg(n) + 1;
}
bool isp(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (isp(a, b)) {
return a;
}
while (!isp(par.at(a), b)) {
if (isp(jump[a], b)) {
a = par[a];
} else {
a = jump[a];
}
}
return par[a];
}
} tree[2];
vector<int> normalize(int n, int root, vector<vector<pair<int, int>>> g) {
vector<int> dist(n, -1);
dist[root] = 0;
vector<bool> used(n);
function<void(int)> dfs = [&](int v) {
used[v] = true;
for (auto [to, w]: g.at(v)) {
if (!used[to]) {
dist[to] = dist[v] + w;
dfs(to);
}
}
};
dfs(root);
return dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, q, t;
cin >> n >> k >> q >> t;
for (int i = 0; i < 2; ++i) {
vector<vector<int>> adj(n);
int root = 0;
for (int j = 0; j < n; ++j) {
int p;
cin >> p;
if (p == -1) {
root = j;
} else {
adj[p - 1].push_back(j);
}
}
tree[i].init(adj, root);
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return tree[0].tin[i] < tree[0].tin[j];
});
ord.resize(k);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return tree[1].tin[i] < tree[1].tin[j];
});
for (int x : ord) {
cout << x + 1 << " \n"[x == ord.back()];
}
vector<pair<int, int>> questions;
for (int i = 1; i < ord.size(); ++i) {
questions.emplace_back(ord[i - 1], ord[i]);
}
for (auto [x, y]: questions) {
cout << "? " << x + 1 << " " << y + 1 << '\n';
}
cout << "!" << endl;
vector g(2, vector<vector<pair<int, int>>>(n));
int h[2]{ord[0], ord[0]};
auto addEdge = [&](int tt, int x, int y, int w) {
g[tt][x].emplace_back(y, w);
g[tt][y].emplace_back(x, -w);
};
for (auto [x, y] : questions) {
for (int i = 0; i < 2; ++i) {
int dx, dy;
cin >> dx >> dy;
int c = tree[i].lca(x, y);
if (tree[i].isp(c, h[i])) {
h[i] = c;
}
addEdge(i, c, x, dx);
addEdge(i, c, y, dy);
}
}
auto first = normalize(n, h[0], g[0]);
auto second = normalize(n, h[1], g[1]);
vector<pair<int, int>> queries(t);
for (auto &[a, b] : queries) {
cin >> a >> b;
a -= 1, b -= 1;
}
for (auto [a, b]: queries) {
int dist1 = first[a] - 2 * first[tree[0].lca(a, b)] + first[b];
int dist2 = second[a] - 2 * second[tree[1].lca(a, b)] + second[b];
cout << dist1 << " " << dist2 << '\n';
}
return 0;
}
