#include <bits/stdc++.h>
using namespace std;
const int maxn=1000000+5;
int r[2];
vector<int> v[2][maxn];
vector<int> f[2][maxn],g[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);
v[1][i].push_back(x);
}
}
}
int cnt=0;
vector<int> p;
int mark[maxn];
void dfsp(int i,int pr)
{
if(cnt==k)return;
cnt++;
p.push_back(i);
mark[i]=1;
for(int j=0;j<v[0][i].size();j++)
{
int nb=v[0][i][j];
dfsp(nb,i);
}
}
vector<pair<int,int> > qr;
int ans[2][maxn];
vector<int> e[2];
int num[2]={1,1};
int w[2][maxn],in[2][maxn];
int op[2][maxn];
int id[2][maxn];
int dep[2][maxn];
void dfsl(int i,int pr,int s)
{
op[s][num[s]]=i;
in[s][i]=num[s]++;
id[s][i]=e[s].size();
e[s].push_back(in[s][i]);
for(int j=0;j<v[s][i].size();j++)
{
int nb=v[s][i][j];
if(nb==pr)continue;
dep[s][nb]=dep[s][i]+1;
dfsl(nb,i,s);
e[s].push_back(in[s][i]);
}
}
int minn[2][2*maxn][32];
int lh[maxn];
void prec()
{
for(int s=0;s<=1;s++)
for(int i=0;i<e[s].size();i++)
minn[s][i][0]=e[s][i];
for(int s=0;s<=1;s++)
for(int j=1;j<=25;j++)
{
for(int i=0;i<e[s].size();i++)
{
if(i+(1<<(j-1))<maxn)
minn[s][i][j]=min(minn[s][i][j-1],minn[s][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,int s)
{
//cout<<x<<" - "<<y<<endl;
x=id[s][x];
y=id[s][y];
if(x>y)swap(x,y);
int len=y-x+1;
len=lh[len];
//cout<<x<<" "<<y<<endl;
int hehe=op[s][min(minn[s][x][len],minn[s][y-(1<<len)+1][len])];
//cout<<"! "<<endl;
return hehe;
}
int last;
void dfsq(int i,int pr)
{
if(mark[i])
{
if(last)qr.push_back({last,i});
last=i;
}
for(int j=0;j<v[1][i].size();j++)
{
int nb=v[1][i][j];
if(nb==pr)continue;
dfsq(nb,i);
}
}
int u[2][maxn];
void die(int i,int pr,int s)
{
//cout<<"!?!? "<<s<<" "<<i<<endl;
u[s][i]=1;
for(int j=0;j<f[s][i].size();j++)
{
int nb=f[s][i][j];
if(u[s][nb])continue;
w[s][nb]=w[s][i]+g[s][i][j];
//cout<<"w "<<s<<" "<<nb<<" "<<w[s][nb]<<endl;
die(nb,i,s);
}
}
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();
dfsq(r[1],-1);
for(int i=0;i<qr.size();i++)
{
cout<<"? "<<qr[i].first<<" "<<qr[i].second<<endl;
}
cout<<"!"<<endl;
cout.flush();
dfsl(r[0],-1,0);
dfsl(r[1],-1,1);
r[1]=p[0];
prec();
for(int i=0;i<qr.size();i++)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
int x=qr[i].first,y=qr[i].second;
int h0=lca(x,y,0),h1=lca(x,y,1);
//cout<<x<<" "<<h1<<" "<<c<<endl;
//cout<<y<<" "<<h1<<" "<<d<<endl;
f[0][x].push_back(y);
g[0][x].push_back(b-a);
f[0][y].push_back(x);
g[0][y].push_back(a-b);
f[1][x].push_back(h1);
g[1][x].push_back(-c);
f[1][h1].push_back(x);
g[1][h1].push_back(c);
f[1][y].push_back(h1);
g[1][y].push_back(-d);
f[1][h1].push_back(y);
g[1][h1].push_back(d);
//cout<<"+ "<<h1<<endl;
if(dep[1][x]<dep[1][r[1]])
r[1]=x;
if(dep[1][y]<dep[1][r[1]])
r[1]=y;
if(dep[1][h1]<dep[1][r[1]])
r[1]=h1;
// w[0][x]-w[0][h0]=a
// w[0][y]-w[0][h0]=b;
// w[1][x]-w[1][h1]=c
// w[1][y]-w[1][h1]=d;
}
//cout<<r[1]<<endl;
/*for(int i=1;i<=n;i++)
{
cout<<w[1][i]<<" "<<i<<": ";
for(int j=0;j<f[1][i].size();j++)
cout<<f[1][i][j]<<" "<<g[1][i][j]<<" / ";
cout<<endl;
}*/
die(r[0],-1,0);
die(r[1],-1,1);
/*for(int i=1;i<=n;i++)
for(int j=0;j<=3;j++)
cout<<i<<" -- "<<j<<" "<<jump[2][i][j]<<" "<<jump[3][i][j]<<endl;*/
for(int i=0;i<t;i++)
{
int x,y;
cin>>x>>y;
int h0=lca(x,y,0),h1=lca(x,y,1);
//cout<<h0<<" + "<<h1<<endl;
ans[0][i]=w[0][x]+w[0][y]-2*w[0][h0];
ans[1][i]=w[1][x]+w[1][y]-2*w[1][h1];
}
for(int i=0;i<t;i++)
cout<<ans[0][i]<<" "<<ans[1][i]<<endl;
cout.flush();
return 0;
}
/*
9 6 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
3 2 0 3
2 12 0 12
5 0 12 9
10 0 0 1
0 3 13 5
1 7
8 5
2 4
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
6 0 0 13
0 3 13 5
1 2
2 7
1 7
*/
