// wa
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXLOG = 18;
int N, K, Q, T;
vector<pair<int,int>> que;
struct tree {
int root;
vector<int> par, dep;
vector<vector<int>> adj;
vector<vector<int>> jmp, dist, jmp2;
vector<int> sub;
tree() {
par.resize(N), adj.resize(N), dep.resize(N);
jmp.resize(MAXLOG, vector<int>(N)), dist.resize(MAXLOG, vector<int>(N)), jmp2.resize(MAXLOG, vector<int>(N));
}
void dfs1(int v) {
if(sub.size() < K) {
sub.push_back(v);
if (v != root) {
que.push_back({par[v], v});
dep[v] = dep[par[v]] + 1;
}
}
for(int &u: adj[v]) {
dfs1(u);
}
}
void build2() {
for(int i = 0; i < N; i++) jmp2[0][i] = (i == root ? i : par[i]);
for(int j = 1; j < MAXLOG; j++) {
for(int i = 0; i < N; i++) {
jmp2[j][i] = jmp2[j-1][jmp2[j-1][i]];
}
}
}
int lcanode(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
int j = MAXLOG - 1;
while(j >= 0) {
if (dep[b] - (1 << j) >= dep[a]) {
b = jmp2[j][b];
}
j--;
}
if (a == b) return a;
j = MAXLOG - 1;
while(j >= 0) {
if (jmp2[j][a] != jmp2[j][b]) {
a = jmp2[j][a], b = jmp2[j][b];
}
j--;
}
return jmp2[0][a];
}
void buildlca() {
for(int j = 1; j < MAXLOG; j++) {
for(int &i: sub) {
dist[j][i] = dist[j-1][jmp[j-1][i]] + dist[j-1][i];
jmp[j][i] = jmp[j-1][jmp[j-1][i]];
}
}
}
int lca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
int re = 0;
int j = MAXLOG - 1;
while(j >= 0) {
if (dep[b] - (1 << j) >= dep[a]) {
re += dist[j][b];
b = jmp[j][b];
}
j--;
}
if (a == b) return re;
j = MAXLOG - 1;
while(j >= 0) {
if (jmp[j][a] != jmp[j][b]) {
re += dist[j][a] + dist[j][b];
a = jmp[j][a], b = jmp[j][b];
}
j--;
}
return re + dist[0][a] + dist[0][b];
}
};
tree one, two;
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin >> N >> K >> Q >> T;
one = {}, two = {};
for(int i = 0; i < N; i++) {
cin >> one.par[i];
one.par[i]--;
if (one.par[i] == -2) one.root = i;
else one.adj[one.par[i]].push_back(i);
}
for(int i = 0; i < N; i++) {
cin >> two.par[i];
two.par[i]--;
if (two.par[i] == -2) two.root = i;
else two.adj[two.par[i]].push_back(i);
}
one.dfs1(one.root);
two.build2();
for(int i = 0; i < one.sub.size() - 1; i++) {
que.push_back({one.sub[i], one.sub[i+1]});
}
for(int &i: one.sub) cout << i+1 << ' ';
cout << '\n';
for(auto &[a, b]: que) cout << "? " << a+1 << ' ' << b+1 << '\n';
cout << '!' << endl;
one.jmp[0][one.root] = one.root;
two.jmp[0][two.root] = two.root;
vector<pair<int,int>> ask(T);
for(int i = 0; i < que.size()/2; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
one.jmp[0][que[i].second] = que[i].first;
one.dist[0][que[i].second] = b;
}
for(int i = 0; i < que.size()/2; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int lca = two.lcanode(que[i].first, que[i].second);
two.jmp[0][que[i].first] = lca;
two.dist[0][que[i].first] = c;
two.jmp[0][que[i].second] = lca;
two.dist[0][que[i].second] = d;
}
for(int i = 0; i < T; i++) cin >> ask[i].first >> ask[i].second;
one.buildlca();
two.buildlca();
for(int i = 0; i < T; i++) {
int x = one.lca(ask[i].first-1, ask[i].second-1);
int y = two.lca(ask[i].first-1, ask[i].second-1);
cout << x << ' ' << y << '\n';
}
cout << endl;
}
