#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int r[2];
vector<int> v[2][maxn];
int n,k,q,t;
void read()
{
cin>>n>>k>>q>>t;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==-1)r[0]=i;
else v[0][x].push_back(i);
}
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==-1)r[1]=i;
else v[1][x].push_back(i);
}
}
int cnt=0;
vector<int> p;
vector<pair<int,int> > v2[maxn];
vector<pair<int,int> > qr;
void dfsp(int i,int pr)
{
if(cnt==k)return;
cnt++;
p.push_back(i);
if(pr!=-1)qr.push_back({pr,i});
for(int j=0;j<v[0][i].size();j++)
{
int nb=v[0][i][j];
dfsp(nb,i);
}
}
int ans[maxn];
vector<int> e;
int num=1;
int w[maxn],in[maxn];
int op[maxn];
int id[maxn];
void dfs2(int i,int p)
{
op[num]=i;
in[i]=num++;
id[i]=e.size();
e.push_back(in[i]);
for(int j=0;j<v2[i].size();j++)
{
int nb=v2[i][j].first;
if(nb==p)continue;
w[nb]=w[i]+v2[i][j].second;
dfs2(nb,i);
e.push_back(in[i]);
}
}
int minn[2*maxn][32];
int lh[maxn];
void prec()
{
for(int i=0;i<e.size();i++)
minn[i][0]=e[i];
for(int j=1;j<=25;j++)
{
for(int i=0;i<e.size();i++)
{
if(i+(1<<(j-1))<maxn)
minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
}
}
for(int i=2;i<maxn;i++)
lh[i]=lh[i/2]+1;
}
int lca(int x,int y)
{
x=id[x];
y=id[x];
if(x>y)swap(x,y);
int len=y-x+1;
len=lh[len];
return op[min(minn[x][len],minn[y-(1<<len)+1][len])];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
dfsp(r[0],-1);
for(int i=0;i<p.size();i++)
cout<<p[i]<<" ";
cout<<endl;
cout.flush();
for(int i=0;i<qr.size();i++)
{
cout<<"? "<<qr[i].first<<" "<<qr[i].second<<endl;
}
cout<<"!"<<endl;
cout.flush();
for(int i=0;i<qr.size();i++)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
int x=max(a,b);
v2[qr[i].first].push_back({qr[i].second,x});
v2[qr[i].second].push_back({qr[i].first,x});
}
dfs2(r[0],-1);
prec();
for(int i=0;i<t;i++)
{
int x,y;
cin>>x>>y;
int h=lca(x,y);
ans[i]={w[x]+w[y]-2*w[h]};
//cout<<h<<"?!?!"<<endl;
}
for(int i=0;i<t;i++)
cout<<ans[i]<<" "<<ans[i]<<endl;
cout.flush();
return 0;
}
