#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
#define forn(i,n) for(int i = 0; i < n; ++i)
#define forr(i,n) for(int i = n-1; i >= 0; --i)
#define forbe(i,b,e) for(int i = b; i < e; ++i)
#define all(v) (v).begin(),(v).end()
#define sort(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define endl '\n';
#define pb push_back
#define ONPC
const int N = 1e6;
const int K = 20;
int cnt = 0;
int n, k, q, t;
vi sv;
using a4 = array<int,4>;
int query(int a, int b){
cout << "? " << a << ' ' << b << endl;
return cnt++;
}
struct tree{
// TODO vectors
vi p;
vector<array<int,K>> j;
vi d;
vi dep;
vector<vi> adj;
int root;
int n;
bitset<N> s;
tree(int _n) {
n = _n;
p.assign(n+3,0);
d.assign(n+3,0);
dep.assign(n+3,0);
j.resize(n+3);
adj.assign(n+3,{});
s = 0;
}
void
build()
{
forbe(i,1,n){
if (p[i] == -1) {
p[i] = i;
root = i;
break;
}
}
forbe(i,1,n){
if (i == root) continue;
adj[p[i]].pb(i);
adj[i].pb(p[i]);
}
}
int
dfs(int i, int k, int par)
{
if (k == 0) return 0;
s[i] = 1;
--k;
sv.pb(i);
if (k == 0) return 0;
for (int u : adj[i]) {
if (u == par) continue;
dep[u] = dep[i]+1;
k = dfs(u, k, i);
if (!k) return 0;
}
return k;
}
void
ask(int i, int par) {
if (!s[i]) return;
j[i][0] = p[i];
if (i != root) {
d[i] = query(i,par);
}
for (int u : adj[i]) {
if (u == par) continue;
ask(u,i);
}
}
void
dfs2(int i, int par) {
if (!s[i]) return;
if (i != root)
d[i] += d[p[i]];
for (int u : adj[i]) {
if (u != par) dfs2(u, i);
}
}
void
build(vi& dist)
{
forn(i, n) {
if (i == root) continue;
if (!s[i]) continue;
d[i] = dist[d[i]];
}
dfs2(root, root);
forbe(k,1, K) {
forn(i, n) {
if (s[i]) j[i][k] = j[j[i][k-1]][k-1];
}
}
}
int
lca(int a, int b){
if (dep[a] < dep[b]) swap(a,b);
for(int k = K-1; k >= 0; --k) {
if (dep[j[a][k]] >= dep[b])
a = j[a][k];
}
if (a == b) return b;
for(int k = K-1; k >= 0; --k) {
if (j[a][k] != j[b][k]) {
a = j[a][k];
b = j[b][k];
}
}
return j[a][0];
}
int
dist(int a, int b)
{
ll d1 = d[a];
ll d2 = d[b];
d1 += d2;
a = lca(a,b);
d2 = d[a];
d2 *= 2l;
d1 -= d2;
return d1;
}
};
#ifdef ONPC
void
solve() {
cin >> n >> k >> q >> t;
tree t1(n+1), t2(n+1);
forn(i, n) cin >> t1.p[i+1];
forn(i, n) cin >> t2.p[i+1];
int a, b;
t1.build();
t2.build();
t1.dfs(t1.root, k, t1.root);
forn(i, k) cout << sv[i] << ' ';
cout << endl;
t1.ask(t1.root, t1.root);
cout << "!" << endl;
cout.flush();
vi dist(cnt);
forn(i, cnt) {
cin >> dist[i] >> a >> b;
cin >> b;
dist[i] = max(dist[i],a);
}
t1.build(dist);
vi ans(t);
forn(i, t) {
cin >> a >> b;
ans[i] = t1.dist(a,b);
}
forn(i,t) cout << ans[i] << ' ' << ans[i] << endl;
cout.flush();
}
int32_t
main(int argc, char** argv) {
if (argc > 1)
freopen(argv[1],"r", stdin);
solve();
}
#endif
