#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const char endl_char = '\n';
// Interactive query: ask distances for nodes a and b
// Reads four integers: d1( lca1, a ), d1( lca1, b ), d2( lca2, a ), d2( lca2, b )
tuple<ll,ll,ll,ll> ask(int a, int b) {
cout << "? " << a << " " << b << "\n" << flush;
ll d1a, d1b, d2a, d2b;
if (!(cin >> d1a >> d1b >> d2a >> d2b)) {
exit(0); // judge closed
}
return {d1a, d1b, d2a, d2b};
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K, Q, T;
cin >> N >> K >> Q >> T;
vector<int> p1(N+1), p2(N+1);
int root1 = -1, root2 = -1;
for(int i = 1; i <= N; i++){
cin >> p1[i];
if(p1[i] == -1) root1 = i;
}
for(int i = 1; i <= N; i++){
cin >> p2[i];
if(p2[i] == -1) root2 = i;
}
// build adjacency of tree1 to select K connected nodes
vector<vector<int>> adj1(N+1);
for(int i = 1; i <= N; i++){
if(p1[i] != -1){
adj1[i].push_back(p1[i]);
adj1[p1[i]].push_back(i);
}
}
// BFS from root1, take first K nodes
vector<int> subset;
subset.reserve(K);
vector<int> parent_in_sub(N+1, -1);
vector<bool> used(N+1, false);
queue<int> q;
q.push(root1);
used[root1] = true;
subset.push_back(root1);
while(!q.empty() && (int)subset.size() < K){
int u = q.front(); q.pop();
for(int v : adj1[u]){
if(!used[v]){
used[v] = true;
parent_in_sub[v] = u;
subset.push_back(v);
q.push(v);
if((int)subset.size() == K) break;
}
}
}
// 1) output chosen subset
for(int i = 0; i < K; i++){
cout << subset[i] << (i+1 < K ? ' ' : '\n');
}
cout << flush;
// 2) ask K-1 queries: for each non-root in subset, ask (parent, node)
// and compute the edge-weights in both trees.
vector<vector<pair<int,ll>>> tree1(K), tree2(K);
// map original label -> index in subset
unordered_map<int,int> idx;
idx.reserve(K*2);
for(int i = 0; i < K; i++){
idx[subset[i]] = i;
}
for(int i = 1; i < K; i++){
int u = subset[i];
int par = parent_in_sub[u];
// ask distances
auto [d1_par, d1_u, d2_par, d2_u] = ask(par, u);
// weight for tree1 edge par-u:
ll w1 = llabs(d1_u - d1_par);
ll w2 = llabs(d2_u - d2_par);
int iu = i, ip = idx[par];
tree1[ip].push_back({iu, w1});
tree1[iu].push_back({ip, w1});
tree2[ip].push_back({iu, w2});
tree2[iu].push_back({ip, w2});
}
// signal end of queries
cout << "!\n" << flush;
// 3) preprocess LCA + dist for both trees on subset nodes
auto build_lca = [&](vector<vector<pair<int,ll>>> &adj,
vector<int>& depth,
vector<ll>& dist,
vector<vector<int>>& up)
{
int LOG = up.size();
int n = adj.size();
function<void(int,int)> dfs = [&](int u, int p){
for(auto [v, w]: adj[u]){
if(v == p) continue;
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
up[0][v] = u;
for(int j = 1; j < LOG; j++){
up[j][v] = up[j-1][ up[j-1][v] ];
}
dfs(v, u);
}
};
// root at index 0
depth[0] = 0; dist[0] = 0;
for(int j = 0; j < LOG; j++) up[j][0] = 0;
dfs(0, -1);
};
int LOG = 1;
while ((1<<LOG) <= K) LOG++;
vector<int> depth1(K), depth2(K);
vector<ll> dist1(K), dist2(K);
vector<vector<int>> up1(LOG, vector<int>(K)),
up2(LOG, vector<int>(K));
build_lca(tree1, depth1, dist1, up1);
build_lca(tree2, depth2, dist2, up2);
auto lca = [&](int u, int v, vector<int>& depth, vector<vector<int>>& up){
if(depth[u] < depth[v]) swap(u,v);
int diff = depth[u] - depth[v];
for(int j = 0; j < LOG; j++){
if(diff & (1<<j)) u = up[j][u];
}
if(u == v) return u;
for(int j = LOG-1; j >= 0; j--){
if(up[j][u] != up[j][v]){
u = up[j][u];
v = up[j][v];
}
}
return up[0][u];
};
// 4) handle T host questions
while(T--){
int pa, pb;
cin >> pa >> pb;
int ia = idx[pa], ib = idx[pb];
// dist in tree1
int c1 = lca(ia, ib, depth1, up1);
ll ans1 = dist1[ia] + dist1[ib] - 2*dist1[c1];
// dist in tree2
int c2 = lca(ia, ib, depth2, up2);
ll ans2 = dist2[ia] + dist2[ib] - 2*dist2[c2];
cout << ans1 << " " << ans2 << "\n";
}
cout << flush;
return 0;
}
