#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mkp make_pair
bool dfsMinimunTree(ll u, ll parent, set<ll>&s, vector<vector<ll>>&tree2, vector<vector<pair<ll,ll>>>&newtree2){
bool co=(s.count(u)>0);
for(ll i=0;i<tree2[u].size();i++){
if(tree2[u][i]==parent)continue;
if(dfsMinimunTree(tree2[u][i],u,s,tree2,newtree2)){
co=true;
newtree2[u].push_back(mkp(tree2[u][i],0));
newtree2[tree2[u][i]].push_back(mkp(u,0));
}
}
return co;
}
void dfsLCA(ll u, ll p, vector<vector<pair<ll,ll>>>&T, vector<vector<ll>>&up, vector<ll>&depth, vector<ll>&dist){
up[0][u]=p;
for(int i=0;i<T[u].size();i++){
if(T[u][i].first==p)continue;
depth[T[u][i].first]=depth[u]+1;
dist[T[u][i].first]=dist[u]+T[u][i].second;
dfsLCA(T[u][i].first,u,T,up,depth,dist);
}
}
void BLCA(vector<vector<pair<ll,ll>>>&T, vector<vector<ll>>&up, vector<ll>&depth, vector<ll>&dist, ll root, ll N, ll K){
ll LOG=1;
while((1<<LOG)<=K)LOG++;
up.assign(LOG,vector<ll>(N+1,0));
depth.assign(N+1,0);
dist.assign(N+1,0);
dfsLCA(root,0,T,up,depth,dist);
for(ll i=1;i<LOG;i++){
for(ll j=1;j<=N;j++){
up[i][j]=up[i-1][j]?up[i-1][up[i-1][j]]:0;
}
}
}
ll GLCA(vector<vector<ll>>&up, vector<ll>&depth, ll a, ll b){
if(depth[a]<depth[b]) swap(a,b);
ll diff=depth[a]-depth[b];
ll LOG=up.size();
for(ll i=0;i<LOG;i++)if(diff & (1<<i))a=up[i][a];
if (a==b) return a;
for(ll i=LOG-1;i>=0;i--){
if(up[i][a] && up[i][a]!=up[i][b]){
a=up[i][a];
b=up[i][b];
}
}
return up[0][a];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll N,K,Q,T;
cin>>N>>K>>Q>>T;
vector<vector<ll>> tree1(N+1,vector<ll>(0)),tree2(N+1,vector<ll>(0));
ll r1=0,r2=0;
for(ll i=1;i<N+1;i++){
ll a;
cin>>a;
if(a==-1){
r1=i;
continue;
}
tree1[a].push_back(i);
tree1[i].push_back(a);
}
for(ll i=1;i<N+1;i++){
ll a;
cin>>a;
if(a==-1){
r2=i;
continue;
}
tree2[a].push_back(i);
tree2[i].push_back(a);
}
queue<ll> q;
q.push(r1);
vector<bool> visited(N+1,false);
ll co=K;
co--;
cout<<r1<<" ";
vector<vector<pair<ll,ll>>> newtree1(N+1,vector<pair<ll,ll>>(0)),newtree2(N+1,vector<pair<ll,ll>>(0));
set<ll> s;
s.insert(r1);
while(q.size() && co>0){
ll nodo=q.front();
q.pop();
visited[nodo]=true;
for(ll i=0;i<tree1[nodo].size() && co>0;i++){
if(visited[tree1[nodo][i]])continue;
newtree1[nodo].push_back(mkp(tree1[nodo][i],0));
co--;
q.push(tree1[nodo][i]);
s.insert(tree1[nodo][i]);
cout<<tree1[nodo][i]<<" ";
}
}
dfsMinimunTree(r2,0,s,tree2,newtree2);
vector<pair<ll,ll>> edges;
for(ll i=1;i<=N;i++){
for(ll j=0;j<newtree1[i].size();j++){
if(i<newtree1[i][j].first) edges.emplace_back(i,newtree1[i][j].first);
}
}
cout<<endl;
for(ll i=0;i<edges.size();i++){
cout<<"? "<<edges[i].first<<" "<<edges[i].second<<'\n';
}
cout<<"!"<<endl;
for(ll i=0;i<edges.size();i++){
ll d1u,d1v,d2u,d2v;
cin>>d1u>>d1v>>d2u>>d2v;
ll peso1=d1u+d1v;
ll peso2=d2u+d2v;
for(ll j=0;j<newtree1[edges[i].first].size();j++){
if(newtree1[edges[i].first][j].first==edges[i].second){
newtree1[edges[i].first][j].second=peso1;
break;
}
}
for(ll j=0;j<newtree1[edges[i].second].size();j++){
if(newtree1[edges[i].second][j].first==edges[i].first){
newtree1[edges[i].second][j].second=peso1;
break;
}
}
for(ll j=0;j<newtree2[edges[i].first].size();j++){
if(newtree2[edges[i].first][j].first==edges[i].second){
newtree2[edges[i].first][j].second=peso2;
break;
}
}
for(ll j=0;j<newtree2[edges[i].second].size();j++){
if(newtree2[edges[i].second][j].first==edges[i].first){
newtree2[edges[i].second][j].second=peso2;
break;
}
}
}
vector<vector<ll>> up1, up2;
vector<ll> depth1, depth2, dist1, dist2;
BLCA(newtree1,up1,depth1,dist1,r1,N,K);
BLCA(newtree2,up2,depth2,dist2,r2,N,K);
vector<pair<ll,ll>> questions(T);
for(int i=0;i<T;i++){
ll u,v;
cin>>u>>v;
questions[i]=mkp(u,v);
}
for(int i=0;i<T;i++){
ll w1=GLCA(up1,depth1,questions[i].first,questions[i].second);
ll w2=GLCA(up2,depth2,questions[i].first,questions[i].second);
ll ans1=dist1[questions[i].first]+dist1[questions[i].second]-2*dist1[w1];
ll ans2=dist2[questions[i].first]+dist2[questions[i].second]-2*dist2[w2];
cout<<ans1<<" "<<ans2<<endl;
}
}
