#include <bits/stdc++.h>
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
struct Tree {
int root = 0;
vector<int> parent;
vector<vector<int>> adj;
void resize(size_t N) {
parent.resize(N);
adj.resize(N);
}
};
struct LCA {
vector<int> first;
vector<int> tourtree;
vector<int> height;
int tree_shift = 0;
void init(Tree& t) {
tree_shift = (1<<__lg(4*(int)t.parent.size()-1+10))+3;
first.resize(tree_shift);
height.resize(tree_shift);
tourtree.assign(2*tree_shift, tree_shift-1);
height[tree_shift-1] = 1e9;
int tour_i = 0;
function<void(int)> dfs = [&](const int u) {
first[u] = tour_i;
//dbg(u, tour_i);
tourtree[tree_shift+tour_i++] = u;
for (int v : t.adj[u]) {
height[v] = height[u]+1;
dfs(v);
tourtree[tree_shift+tour_i++] = u;
}
};
dfs(t.root);
for (int i = tree_shift-1; i > 0; i--) {
tourtree[i] = min(make_pair(height[tourtree[2*i]], tourtree[2*i]), make_pair(height[tourtree[2*i+1]], tourtree[2*i+1])).second;
}
}
int lca(int l, int r) {
if (first[l] > first[r]) swap(l, r);
/*cerr << "\n-----------\n";
for (int i = 0; i < tree_shift; i++) {
cerr << tourtree[tree_shift+i] << " ";
}
cerr << "\n\n-----------\n" << endl;
dbg(tree_shift);*/
l = first[l]+tree_shift, r = first[r]+tree_shift+1;
//cerr << "lr " << l << " " << r << endl;
pair<int,int> ret(1e9, 1e9);
for (; l < r; l >>= 1, r >>= 1) {
if (l&1) {
ret = min(ret, make_pair(height[tourtree[l]], tourtree[l]));
//dbg(tourtree[l], height[tourtree[l]]);
l++;
}
if (r&1) {
--r;
ret = min(ret, make_pair(height[tourtree[r]], tourtree[r]));
}
}
return ret.second;
}
};
istream& operator>>(istream& in, Tree& tree) {
for (size_t i = 0; i < tree.parent.size(); i++) {
in >> tree.parent[i], tree.parent[i]--;
if (tree.parent[i] == -2) {
tree.parent[i] = -1;
tree.root = i;
} else {
tree.adj[tree.parent[i]].push_back(i);
}
}
return in;
}
int N, K, Q, T;
Tree trees[2];
vector<int> chosen_set;
LCA lca[2];
namespace com {
void choose_set(vector<int>& v) {
for (int i = 0; i < K; i++) {
cout << v[i]+1 << (i == K-1 ? '\n' : ' ');
}
cout << flush;
}
void query(int u, int v) {
cout << "? " << u+1 << " " << v+1 << '\n';
Q++;
}
pair<vector<array<int,4>>,vector<pair<int,int>>> read_response() {
cout << "!\n" << flush;
vector<array<int,4>> resp(Q);
vector<pair<int,int>> queries(T);
for (int i = 0; i < Q; i++)
for (int j = 0; j < 4; j++)
cin >> resp[i][j];
for (int i = 0; i < T; i++)
cin >> queries[i].first >> queries[i].second, queries[i].first--, queries[i].second--;
return make_pair(resp, queries);
}
void answer(int d1, int d2) {
cout << d1 << " " << d2 << '\n';
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> N >> K >> Q >> T;
Q = 0;
for (int i = 0; i < 2; i++) {
trees[i].resize(N);
cin >> trees[i];
}
function<void(int)> dfs = [&](const int u) {
if ((int)chosen_set.size() < K) chosen_set.push_back(u);
for (int v : trees[0].adj[u]) dfs(v);
};
dfs(trees[0].root);
sort(chosen_set.begin(), chosen_set.end());
com::choose_set(chosen_set);
lca[1].init(trees[1]);
lca[0].init(trees[0]);
sort(chosen_set.begin(), chosen_set.end(), [](const int a, const int b) {
return lca[1].first[a] < lca[1].first[b];
});
vector<int> elems;
vector<int> poselem(N, -1);
vector<int> cumulsum = {0};
for (int i = 0; i < K-1; i++) {
elems.push_back(chosen_set[i]);
poselem[elems.back()] = elems.size()-1;
//dbg(i, elems.back());
//dbg(chosen_set[i], chosen_set[i+1], lca[1].lca(chosen_set[i], chosen_set[i+1]));
elems.push_back(lca[1].lca(chosen_set[i], chosen_set[i+1]));
poselem[elems.back()] = elems.size()-1;
//dbg(i, elems.back());
com::query(chosen_set[i], chosen_set[i+1]);
}
elems.push_back(chosen_set.back());
poselem[elems.back()] = elems.size()-1;
/*cout << "\n\n\n";
dbg(chosen_set);
dbg(elems);
cout << "\n\n\n";*/
//vector<pair<int,int>> infotree0(N);
//for (int i = 0; i < N; i++) infotree0[i] = make_pair(i, 0);
//vector<int> sumuntilroot(N);
//vector<int> w_edge(N);
auto [resp, queries] = com::read_response();
vector<vector<pair<int,int>>> newadj(N);
vector<int> sumuntilroot(N, -1);
for (int i = 0; i < Q; i++) {
cumulsum.push_back(cumulsum.back()+resp[i][2]);
cumulsum.push_back(cumulsum.back()-resp[i][3]);
int a = lca[0].lca(elems[2*i], elems[2*i+2]);
//cerr << "pair " << a << " " << elems[2*i] << " " << resp[i][0] << endl;
newadj[a].emplace_back(elems[2*i], resp[i][0]);
newadj[elems[2*i]].emplace_back(a, -resp[i][0]);
newadj[a].emplace_back(elems[2*i+2], resp[i][1]);
newadj[elems[2*i+2]].emplace_back(a, -resp[i][1]);
}
// à vérifier
function<void(int)> dfs2 = [&](const int u) {
for (auto [v, sumw] : newadj[u]) {
if (sumuntilroot[v] == -1) {
sumuntilroot[v] = sumuntilroot[u]+sumw;
dfs2(v);
}
}
};
sumuntilroot[trees[0].root] = 0;
dfs2(trees[0].root);
/*for (int u = 0; u < N; u++) {
if (newadj[u].size()) cerr << "sumuntil " << u << " = " << newadj[u][0].first << ":" << newadj[u][0].second << endl;
}*/
for (int i = 0; i < T; i++) {
auto& q = queries[i];
int d1 = -2*sumuntilroot[lca[0].lca(q.first, q.second)]+sumuntilroot[q.first]+sumuntilroot[q.second];
//dbg(q.first, q.second);
//dbg(poselem[q.first], poselem[q.second]);
int d2 = 2*cumulsum[poselem[lca[1].lca(q.first, q.second)]]-cumulsum[poselem[q.first]]-cumulsum[poselem[q.second]];
com::answer(d1, d2);
}
}
