#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, K, Q, T;
struct MinSegtree{
int n;
vector<pair<int, int>> tree;
void init(vector<pair<int, int>> val) {
n = val.size();
tree = vector<pair<int, int>>(2*n, {INT_MAX, INT_MAX});
for (int i = 0; i < n; i++) tree[n+i] = val[i];
for (int i = n-1; i >= 1; i--) tree[i] = min(tree[i<<1], tree[(i<<1)|1]);
}
pair<int, int> query(int l, int r) {
r++;
pair<int, int> ret = {INT_MAX, INT_MAX};
for (l += n, r += n; l < r; l>>=1, r>>=1) {
if (l&1) ret = min(ret, tree[l++]);
if (r&1) ret = min(ret, tree[--r]);
}
return ret;
}
};
struct Tree{
int n, root;
vector<int> p;
vector<vector<int>> child;
vector<int> tin, depth, ord;
MinSegtree segtree;
int cte = -1;
void gen_ett(int u) {
tin[u] = ++cte;
ord.push_back(u);
for (int v : child[u]) {
depth[v] = depth[u]+1;
gen_ett(v);
++cte;
ord.push_back(u);
}
}
void readtree(int _n) {
n = _n;
p = tin = depth = vector<int>(n);
child = vector<vector<int>>(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
if (p[i] == -1) root = i;
else {
p[i]--; // Change 1-based index to 0-based index
child[p[i]].push_back(i);
}
}
depth[root] = 0;
gen_ett(root);
vector<pair<int, int>> tmp(ord.size());
for (int i = 0; i < ord.size(); i++)
tmp[i] = make_pair(depth[ord[i]], ord[i]);
segtree.init(tmp);
}
vector<int> sort_by_tin(vector<int> x) {
sort(x.begin(), x.end(), [this](int a, int b) {
return tin[a] < tin[b];
});
return x;
}
int lca(int u, int v) {
return segtree.query(min(tin[u], tin[v]), max(tin[u], tin[v])).second;
}
} tree1, tree2;
struct EqSolver{
int n;
vector<vector<pair<int, ll>>> edge;
vector<ll> result;
void init(int _n, vector<int> a, vector<int> b, vector<ll> c, int root) {
n = _n;
edge = vector<vector<pair<int, ll>>>(n);
result = vector<ll>(n);
for (int i = 0; i < a.size(); i++) {
edge[a[i]].emplace_back(b[i], -c[i]);
edge[b[i]].emplace_back(a[i], c[i]);
}
vector<bool> vis(n);
queue<int> bfs;
bfs.push(root);
while (!bfs.empty()) {
int u = bfs.front();
bfs.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto [v, w] : edge[u]) {
if (!vis[v]) {
result[v] = result[u]+w;
bfs.push(v);
}
}
}
}
} solver1, solver2;
pair<vector<array<int, 4>>, vector<pair<int, int>>> query(vector<int> x, vector<int> u, vector<int> v) {
for (int i : x)
cout << i+1 << " "; // Change 0-based index to 1-based index
cout << endl;
int q = u.size();
for (int i = 0; i < q; i++)
cout << "? " << u[i]+1 << " " << v[i]+1 << "\n"; // Change 0-based index to 1-based index
cout << "!" << endl;
vector<array<int, 4>> ret1(q);
for (int i = 0; i < q; i++) cin >> ret1[i][0] >> ret1[i][1] >> ret1[i][2] >> ret1[i][3];
vector<pair<int, int>> ret2(T);
for (int i = 0; i < T; i++) {
cin >> ret2[i].first >> ret2[i].second;
ret2[i].first--; ret2[i].second--; // Change 1-based index to 0-based index
}
return make_pair(ret1, ret2);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K >> Q >> T;
tree1.readtree(N);
tree2.readtree(N);
vector<int> x(N);
iota(x.begin(), x.end(), 0);
x = tree1.sort_by_tin(x);
x.resize(K);
x = tree2.sort_by_tin(x);
vector<int> u(K-1), v(K-1);
for (int i = 0; i < K-1; i++) u[i] = x[i], v[i] = x[i+1];
auto [query_results, questions] = query(x, u, v);
// Create solver1
{
vector<int> a(2*(K-1)), b(2*(K-1));
vector<ll> c(2*(K-1));
for (int i = 0; i < K-1; i++) {
int lca_node = tree1.lca(u[i], v[i]);
a[2*i] = u[i];
b[2*i] = lca_node;
c[2*i] = query_results[i][0];
a[2*i+1] = v[i];
b[2*i+1] = lca_node;
c[2*i+1] = query_results[i][1];
}
solver1.init(N, a, b, c, u[0]);
}
// Create solver2
{
vector<int> a(2*(K-1)), b(2*(K-1));
vector<ll> c(2*(K-1));
for (int i = 0; i < K-1; i++) {
int lca_node = tree2.lca(u[i], v[i]);
a[2*i] = u[i];
b[2*i] = lca_node;
c[2*i] = query_results[i][2];
a[2*i+1] = v[i];
b[2*i+1] = lca_node;
c[2*i+1] = query_results[i][3];
}
solver2.init(N, a, b, c, u[0]);
}
for (auto [a, b] : questions) {
ll ans1 = solver1.result[a] + solver1.result[b] - 2*solver1.result[tree1.lca(a, b)];
ll ans2 = solver2.result[a] + solver2.result[b] - 2*solver2.result[tree2.lca(a, b)];
cout << ans1 << " " << ans2 << "\n";
}
cout << endl;
return 0;
}
/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
*/
/*
10 0 0 1
0 3 13 5
4 2
4 1
1 2
*/
