#include <bits/stdc++.h>
using namespace std;
/** 1-indexed LCA class */
class least_common_ancestor {
private:
int n, max_log, dfs_cnt = 0, root;
vector< vector< pair<int, int> > > g;
vector< vector<int> > up;
vector<int> d, dfs_in, dfs_out;
void dfs(int u, int p) {
dfs_in[u] = dfs_cnt++;
up[u][0] = p;
for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (auto &v : g[u]) {
if (v.first == u) continue;
d[v.first] = d[u] + v.second;
dfs(v.first, u);
}
dfs_out[u] = dfs_cnt;
}
void init() {
n = (int) g.size() - 1;
max_log = ceil(log2(n + 1));
up.assign(n + 1, vector<int>(max_log + 1));
d.assign(n + 1, 0);
dfs_in.resize(n + 1);
dfs_out.resize(n + 1);
dfs(root, root);
}
public:
/** Assumes g is an undirected tree. Can be directed if edges point away from vertex the root */
least_common_ancestor(const vector< vector< pair<int, int> > > &_g, int _root = 1) : root(_root), g(_g) {
init();
}
/** Assigns weight 1 to all edges in an unweighted tree */
least_common_ancestor(const vector< vector<int> > &_g, int _root = 1) : root(_root) {
g.assign((int) _g.size(), vector< pair<int, int> >());
for (int i = 0; i < (int) _g.size(); i++) {
for (auto &x : _g[i]) g[i].emplace_back(x, 1);
}
init();
}
bool is_anc(int u, int v) {
return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
}
int query(int u, int v) {
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int i = max_log; i >= 0; i--) {
if (!is_anc(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
int depth(int u) {
return d[u];
}
int dist(int u, int v) {
return d[u] + d[v] - 2 * d[query(u, v)];
}
int preorder(int u) {
return dfs_in[u];
}
int postorder(int u) {
return dfs_out[u];
}
};
vector< vector< pair<int, int> > > v_g[2];
void dfs(int u, vector<int> &dist, const vector< vector< pair<int, int> > > &g) {
if (dist[u] == -1) dist[u] = 0;
for (auto &v : g[u]) {
if (dist[v.first] == -1) {
dist[v.first] = dist[u] + v.second;
dfs(v.first, dist, g);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, q, t;
cin >> n >> k >> q >> t;
int r[2];
vector<int> p[2];
vector< vector<int> > g[2];
for (int idx = 0; idx < 2; idx++) {
p[idx].resize(n + 1);
g[idx].resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[idx][i];
if (p[idx][i] == -1) r[idx] = i;
else g[idx][p[idx][i]].push_back(i);
}
}
least_common_ancestor lca[2] = {least_common_ancestor(g[0], r[0]), least_common_ancestor(g[1], r[1])};
vector<int> x(n);
iota(x.begin(), x.end(), 1);
sort(x.begin(), x.end(), [&](int a, int b) {
return lca[0].preorder(a) < lca[0].preorder(b);
});
x.erase(x.begin() + k, x.end());
sort(x.begin(), x.end(), [&](int a, int b) {
return lca[1].preorder(a) < lca[1].preorder(b);
});
vector<int> pos(n + 1, -1);
for (int i = 0; i < k; i++) {
if (i > 0) cout << ' ';
cout << x[i];
pos[x[i]] = i;
}
cout << endl;
vector<int> virtual_tree = x;
for (int i = 1; i < k; i++) {
cout << "? " << x[i - 1] << ' ' << x[i] << endl;
virtual_tree.push_back(lca[1].query(x[i - 1], x[i]));
}
cout << "!" << endl;
sort(virtual_tree.begin(), virtual_tree.end(), [&](int a, int b) {
return lca[1].preorder(a) < lca[1].preorder(b);
});
virtual_tree.erase(unique(virtual_tree.begin(), virtual_tree.end()), virtual_tree.end());
int v_r = virtual_tree[0];
vector<int> l_0(k), r_0(k), l_1(k), r_1(k);
v_g[0].assign(n + 1, vector< pair<int, int> >());
v_g[1].assign(n + 1, vector< pair<int, int> >());
for (int i = 1; i < k; i++) {
cin >> l_0[i] >> r_0[i] >> l_1[i] >> r_1[i];
int p_0 = lca[0].query(x[i - 1], x[i]), p_1 = lca[1].query(x[i - 1], x[i]);
v_g[0][p_0].emplace_back(x[i - 1], l_0[i]);
v_g[0][x[i - 1]].emplace_back(p_0, -l_0[i]);
v_g[0][p_0].emplace_back(x[i], r_0[i]);
v_g[0][x[i]].emplace_back(p_0, -r_0[i]);
v_g[1][p_1].emplace_back(x[i - 1], l_1[i]);
v_g[1][x[i - 1]].emplace_back(p_1, -l_1[i]);
v_g[1][p_1].emplace_back(x[i], r_1[i]);
v_g[1][x[i]].emplace_back(p_1, -r_1[i]);
}
vector<int> d_0(n + 1, -1), d_1(n + 1, -1);
dfs(r[0], d_0, v_g[0]); dfs(v_r, d_1, v_g[1]);
vector< pair<int, int> > queries(t);
for (int i = 0; i < t; i++) cin >> queries[i].first >> queries[i].second;
for (auto &e : queries) {
int u = e.first, v = e.second;
cout << d_0[u] + d_0[v] - 2 * d_0[lca[0].query(u, v)] << ' ' << d_1[u] + d_1[v] - 2 * d_1[lca[1].query(u, v)] << endl;
}
return 0;
}
