#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int r[2];
vector<int> v[4][maxn];
vector<int> g[4][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 dep[maxn];
int mark[maxn];
void dfsp(int i,int pr)
{
if(cnt==k)return;
cnt++;
p.push_back(i);
mark[i]=1;
if(pr!=-1)dep[i]=dep[pr]+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[4][maxn],in[2][maxn];
int op[2][maxn];
int id[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;
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)
{
x=id[s][x];
y=id[s][y];
if(x>y)swap(x,y);
int len=y-x+1;
len=lh[len];
return op[s][min(minn[s][x][len],minn[s][y-(1<<len)+1][len])];
}
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 jump[4][maxn][25];
int dep2[4][maxn];
int lca2(int x,int y,int s)
{
if(dep2[s][x]<dep2[s][y])swap(x,y);
//cout<<x<<" !!! "<<y<<endl;
for(int i=25;i>=0;i--)
{
if(dep2[s][x]-dep2[s][y]>=(1<<i))
{
x=jump[s][x][i];
}
}
if(x==y)return x;
for(int i=25;i>=0;i--)
{
if(jump[s][x][i]!=jump[s][y][i])
{
x=jump[s][x][i];
y=jump[s][y][i];
}
}
return jump[s][x][0];
}
int u[4][maxn];
void die(int i,int pr,int s)
{
//cout<<"!?!? "<<s<<" "<<i<<endl;
u[s][i]=1;
for(int j=0;j<v[s][i].size();j++)
{
int nb=v[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;
dep2[s][nb]=dep2[s][i]+1;
jump[s][nb][0]=i;
for(int jj=1;jj<=20;jj++)
jump[s][nb][jj]=jump[s][jump[s][nb][jj-1]][jj-1];
die(nb,i,s);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
dfsp(r[0],-1);
mark[p[k-1]]=0;
mark[r[1]]=1;
p.pop_back();
p.push_back(r[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);
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;
v[2][x].push_back(y);
g[2][x].push_back(b-a);
v[2][y].push_back(x);
g[2][y].push_back(a-b);
v[3][x].push_back(h1);
g[3][x].push_back(-c);
v[3][h1].push_back(x);
g[3][h1].push_back(c);
v[3][y].push_back(h1);
g[3][y].push_back(-d);
v[3][h1].push_back(y);
g[3][h1].push_back(d);
// 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;
}
die(r[0],-1,2);
die(r[1],-1,3);
/*for(int i=1;i<=n;i++)
{
cout<<w[3][i]<<" "<<i<<": ";
for(int j=0;j<v[3][i].size();j++)
cout<<v[3][i][j]<<" "<<g[3][i][j]<<" / ";
cout<<endl;
}*/
/*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,2),h1=lca(x,y,3);
//cout<<h0<<" + "<<h1<<endl;
ans[2][i]=w[2][x]+w[2][y]-2*w[2][h0];
ans[3][i]=w[3][x]+w[3][y]-2*w[3][h1];
}
for(int i=0;i<t;i++)
cout<<ans[2][i]<<" "<<ans[3][i]<<endl;
return 0;
}
/*
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
*/
