#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
#define cin fin
#define cout fout
string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/
#define ull unsigned long long
#define ll long long
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 1e6 + 10, K = 20;
struct tree{
vector<pii> a[N];
vector<int> g[N];
int up[N][K], dp[N], tin[N], depth[N];
vector<int> pre;
int root = -1;
int timein = 0;
void dfs(int u, int p){
up[u][0] = p;
pre.push_back(u);
depth[u] = depth[p] + 1;
tin[u] = ++timein;
for(int j = 1; j < K; j++)
up[u][j] = up[up[u][j - 1]][j - 1];
for(auto i : g[u])
if(i != p){
dfs(i, u);
}
}
int lca(int u, int v){
if(depth[u] > depth[v])
swap(u, v);
for(int j = K - 1; j >= 0; j--)
if(depth[u] <= depth[up[v][j]])
v = up[v][j];
if(u == v)
return u;
for(int j = K - 1; j >= 0; j--)
if(up[u][j] != up[v][j])
u = up[u][j], v = up[v][j];
return up[u][0];
}
void add(int u, int v, int w1, int w2){
int l = lca(u, v);
if(root == -1 || depth[l] < depth[root])
root = l;
a[l].push_back({u, w1});
a[u].push_back({l, w1});
a[l].push_back({v, w2});
a[v].push_back({l, w2});
}
void solve(){
queue<int> q;
q.push(root);
while(!q.empty()){
int s = q.front();
q.pop();
for(auto [u, w] : a[s]){
if(dp[u] == 0 && u != s && u != root)
dp[u] = dp[s] + (depth[u] >= depth[s] ? w : -w), q.push(u);
}
}
}
int query(int u, int v){
int l = lca(u, v);
return dp[u] + dp[v] - (2 * dp[l]);
}
}a1, a2;
int n, k, q, t;
void solve(){
cin >> n >> k >> q >> t;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
if(x == -1)
a1.root = i;
else{
a1.g[x].push_back(i);
a1.g[i].push_back(x);
}
}
for(int i = 1; i <= n; i++){
int x;
cin >> x;
if(x == -1)
a2.root = i;
else{
a2.g[x].push_back(i);
a2.g[i].push_back(x);
}
}
a1.dfs(a1.root, a1.root);
a2.dfs(a2.root, a2.root);
vector<int> aux;
for(int i = 0; i < k; i++)
aux.push_back(a1.pre[i]);
for(auto i : aux)
cout << i << ' ';
cout << endl;
sort(all(aux), [&] (int i, int j){
return a2.tin[i] < a2.tin[j];
});
for(int i = 0; i < k - 1; i++)
cout << "? " << aux[i] << ' ' << aux[i + 1] << '\n';
cout << "!" << endl;
a1.root = a2.root = -1;
for(int i = 0; i < k - 1; i++){
int w1, w2, w3, w4;
cin >> w1 >> w2 >> w3 >> w4;
a1.add(aux[i], aux[i + 1], w1, w2);
a2.add(aux[i], aux[i + 1], w3, w4);
}
a1.solve();
a2.solve();
vector<pii> ans;
for(int i = 0; i < t; i++){
int x, y;
cin >> x >> y;
ans.push_back({a1.query(x, y), a2.query(x, y)});
}
for(auto i : ans)
cout << i.first << ' ' << i.second << '\n';
cout << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
