#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6+5;
const int LOG = log2(N)+2;
vector<int> g1[N], g2[N];
vector<pair<int,int> > wg[N][2];
int k;
int tin[N][2], tout[N][2], tt[2];
int par[N][LOG][2], dist[N][2];
bool chos[N];
vector<int> nodes;
vector<pair<int,int> > qu;
void dfs1(int u, int p)
{
nodes.pb(u);
k--;
chos[u]=1;
par[u][0][0]=p;
tin[u][0]=++tt[0];
for(int i = 1;i<LOG;i++)
par[u][i][0]=par[par[u][i-1][0]][i-1][0];
for(auto v:g1[u])
if(k>0&&v!=p)
dfs1(v,u);
tout[u][0]=tt[0];
}
void dfs2(int u, int p)
{
tin[u][1]=++tt[1];
par[u][0][1]=p;
for(int i = 1;i<LOG;i++)
par[u][i][1]=par[par[u][i-1][1]][i-1][1];
for(auto v:g2[u])
if(v!=p)
dfs2(v,u);
tout[u][1]=tt[1];
}
bool isanc(int u, int v, int t)
{
return (tin[u][t]<=tin[v][t]&&tout[v][t]<=tout[u][t]);
}
int getlca(int u, int v, int t)
{
if(isanc(u,v,t))
return u;
if(isanc(v,u,t))
return v;
for(int i = LOG-1;i>=0;i--)
if(!isanc(par[u][i][t],v,t))
u=par[u][i][t];
return par[u][0][t];
}
void calcq()
{
sort(nodes.begin(),nodes.end(),[&](int &i, int &j){return (tin[i][1]<tin[j][1]);});
for(int i = 1;i<nodes.size();i++)
qu.pb({nodes[i-1],nodes[i]});
}
void addedge(int u, int v, int w, int t)
{
wg[u][t].pb({v,w});
wg[v][t].pb({u,-w});
}
void dfs3(int u, int t)
{
for(auto v:wg[u][t])
{
int nwd = dist[u][t]+v.se;
if(dist[v.fi][t]>nwd)
dist[v.fi][t]=nwd,
dfs3(v.fi,t);
}
}
int getdist(int u, int v, int t)
{
ll d1 = dist[u][t], d2 = dist[v][t];
int lca = getlca(u,v,t);
ll d3 = dist[lca][t];
return d1+d2-d3*2;
}
int main()
{
fio
// ifstream cin("in.in");
int n, q, t;
cin >> n >> k >> q >> t;
int r1, r2;
for(int i = 1;i<=n;i++)
{
int p;
cin >> p;
if(p==-1)
r1=i;
else
g1[p].pb(i);
}
for(int i = 1;i<=n;i++)
{
int p;
cin >> p;
if(p==-1)
r2=i;
else
g2[p].pb(i);
}
dfs1(r1,r1);
dfs2(r2,r2);
calcq();
for(auto x:nodes)
cout << x << " ";
cout << endl;
for(auto x:qu)
cout << "? " << x.fi << " " << x.se << "\n";
cout << "!" << endl;
r2=-1;
for(auto x:qu)
{
int d11, d12, d21, d22;
cin >> d11 >> d12 >> d21 >> d22;
int lca1 = getlca(x.fi,x.se,0), lca2 = getlca(x.fi,x.se,1);
addedge(lca1,x.fi,d11,0);
addedge(lca1,x.se,d12,0);
addedge(lca2,x.fi,d21,1);
addedge(lca2,x.se,d22,1);
if(r2==-1||tin[lca2][1]<tin[r2][1])
r2=lca2;
}
for(int i = 1;i<=n;i++)
dist[i][0]=dist[i][1]=2e9+5;
dist[r1][0]=dist[r2][1]=0;
dfs3(r1,0);
dfs3(r2,1);
vector<pair<int,int> > ans(t);
for(int i = 0;i<t;i++)
{
int u, v;
cin >> u >> v;
ans[i]={getdist(u,v,0),getdist(u,v,1)};
}
for(auto x:ans)
cout << x.fi << " " << x.se << "\n";
return 0;
}
