#include <bits/stdc++.h>
using namespace std;
int n, k, q, t;
struct tree {
vector<vector<int>> c;
vector<array<int, 20>> jmp;
int root;
vector<int> depth;
vector<vector<pair<int, int>>> extraEdges;
vector<int> dist;
tree(vector<int> p) {
c.resize(n);
jmp.resize(n);
extraEdges.resize(n);
dist.resize(n, INT_MIN);
depth.resize(n);
for (int i = 0; i < p.size(); i++) {
if (p[i] == -1) {
p[i] = i;
root = i;
} else {
p[i]--;
c[p[i]].push_back(i);
}
}
for (int i = 0; i < n; i++) {
jmp[i][0] = p[i];
}
dfs(root);
}
void dfs(int v, int d = 0) {
depth[v] = d;
for (int i = 1; i < 20; i++) {
jmp[v][i] = jmp[jmp[v][i-1]][i-1];
}
for (int u: c[v]) {
dfs(u, d+1);
}
}
int jump(int v, int steps) {
for (int i = 0; i < 20; i++) {
if (steps & (1 << i)) {
v = jmp[v][i];
}
}
return v;
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
a = jump(a, depth[a] - depth[b]);
if (a == b) return a;
for (int i = 19; i >= 0; i--) {
if (jmp[a][i] != jmp[b][i]) {
a = jmp[a][i];
b = jmp[b][i];
}
}
return jmp[a][0];
}
void addEdge(int a, int b, int w) {
extraEdges[a].push_back({b, w});
extraEdges[b].push_back({a, -w});
}
void dfs_dist(int v, int d) {
if (dist[v] != INT_MIN) return;
dist[v] = d;
for (auto [u, w]: extraEdges[v]) {
dfs_dist(u, d + w);
}
}
void process(int x) {
dfs_dist(x, 0);
}
int solve(int a, int b) {
int p = lca(a, b);
if (dist[a] == INT_MIN || dist[b] == INT_MIN || dist[p] == INT_MIN) {
cerr << "Error: distance not found\n";
return -1;
}
return dist[a] + dist[b] - 2*dist[p];
}
vector<int> preorder() {
vector<int> res;
dfs_preorder(root, res);
return res;
}
void dfs_preorder(int v, vector<int>& res) {
res.push_back(v);
for (int u: c[v]) {
dfs_preorder(u, res);
}
}
};
tree read_tree() {
vector<int> p(n);
for (int i = 0; i < n; i++) cin >> p[i];
return tree(p);
}
int main() {
cin >> n >> k >> q >> t;
tree t1 = read_tree();
tree t2 = read_tree();
vector<int> o1 = t1.preorder();
vector<int> o2 = t2.preorder();
vector<int> o2inv(n);
for (int i = 0; i < n; i++) {
o2inv[o2[i]] = i;
}
vector<int> x(o1.begin(), o1.begin() + k);
sort(x.begin(), x.end(), [&](int a, int b) {
return o2inv[a] < o2inv[b];
});
for (int i = 0; i < k; i++) {
if (i) cout << " ";
cout << x[i]+1;
}
cout << "\n";
for (int i = 0; i < k-1; i++) {
cout << "? " << x[i]+1 << " " << x[i+1]+1 << "\n";
}
cout << "!\n";
cout.flush();
for (int i = 0; i < k-1; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int lca1 = t1.lca(x[i], x[i+1]);
int lca2 = t2.lca(x[i], x[i+1]);
t1.addEdge(lca1, x[i], a);
t1.addEdge(lca1, x[i+1], b);
t2.addEdge(lca2, x[i], c);
t2.addEdge(lca2, x[i+1], d);
#define LOG
cout << "Tree 1: Adding edge " << lca1+1 << " - " << x[i]+1 << " with weight " << a << "\n";
cout << "Tree 1: Adding edge " << lca1+1 << " - " << x[i+1]+1 << " with weight " << b << "\n";
cout << "Tree 2: Adding edge " << lca2+1 << " - " << x[i]+1 << " with weight " << c << "\n";
cout << "Tree 2: Adding edge " << lca2+1 << " - " << x[i+1]+1 << " with weight " << d << "\n";
#endif
}
t1.process(x[0]);
t2.process(x[0]);
#ifdef LOG
for (int i = 0; i < n; i++) {
if (t1.dist[i] != INT_MIN) {
cout << "Tree 1: Depth of node " << i+1 << " is " << t1.dist[i] << "\n";
}
}
for (int i = 0; i < n; i++) {
if (t2.dist[i] != INT_MIN) {
cout << "Tree 2: Depth of node " << i+1 << " is " << t2.dist[i] << "\n";
}
}
#endif
vector<pair<int, int>> queries;
for (int i = 0; i < t; i++) {
int a, b;
cin >> a >> b;
a--; b--;
queries.push_back({a, b});
}
for (auto [a, b]: queries) {
cout << t1.solve(a, b) << " " << t2.solve(a, b) << "\n";
}
}
/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
3 0 5 13
0 1 10 7
1 2
2 3
3 1
5 2 1 4
3 3 5 1 -1
3 4 -1 5 1
1436 0 0 559
3 5
3 5
3 5
3 5
*/
