#include<bits/stdc++.h>
using namespace std;
inline void Flu(){fflush(stdout);}
const int maxm=100025;
const int maxn=1000025;
int n,K,Q,T,m,i,j,t,k,s,Log[maxn];
struct Edge
{
	int nxt,aim;
};
bool lit[maxn];
int seq[maxm],tsq,stk[maxm],tp,tof[maxm],quer[maxm][4],ord[maxm];
struct Tree
{
	int N,head[maxn],nrt,fat[maxn][21],dfn[maxn],bac[maxn];
	int dep[maxn],tod[maxn],dep2[maxn];
	Edge edge[maxn];
	inline void add_edge(int x,int y)
	{
		if (x==-1){nrt=y;return;}
		fat[y][0]=x;
		edge[++N]=(Edge){head[x],y};head[x]=N;
		//edge[++N]=(Edge){head[y],x};head[y]=N;
	}
	void dfs_gt_seq(int x)
	{
		lit[x]=1;ord[++tsq]=x;if (tsq>=K) return;
		for (int i=head[x];i;i=edge[i].nxt)
		{
			int des=edge[i].aim;
			dfs_gt_seq(des);if (tsq>=K) return;
		}
	}
	void dfs1(int x)
	{
		dfn[x]=++t;bac[t]=x;dep[x]=dep[fat[x][0]]+1;
		for (int i=1;i<=Log[n];++i) fat[x][i]=fat[fat[x][i-1]][i-1];
		for (int i=head[x];i;i=edge[i].nxt)
		{
			int des=edge[i].aim;
			dfs1(des);
		}
	}
	int LCA(int x,int y)
	{
		if (dep[x]<dep[y]) swap(x,y);
		for (int i=Log[n];~i;--i) if (dep[fat[x][i]]>=dep[y]) x=fat[x][i];
		if (x==y) return x;
		for (int i=Log[n];~i;--i) if (fat[x][i]^fat[y][i])
		 x=fat[x][i],y=fat[y][i];
		return fat[x][0];
	}
	void dfs2(int x)
	{
		dep2[x]=dep2[fat[x][0]]+tod[x];
		for (int i=head[x];i;i=edge[i].nxt)
		{
			int des=edge[i].aim;
			dfs2(des);
		}
	}
	void Process1()
	{
		tsq=0;
		for (int i=1;i<=n;++i)
		 if (lit[bac[i]]) seq[++tsq]=bac[i];
		for (int i=1;i<=tsq;++i) printf("%d ",seq[i]);puts("");
		for (int i=1;i<tsq;++i) printf("? %d %d\n",seq[i],seq[i+1]);
		puts("!");Flu();
		for (int i=1;i<tsq;++i)
		 scanf("%d%d%d%d",&quer[i][0],&quer[i][1],
		  &quer[i][2],&quer[i][3]);
		stk[tp=1]=seq[1];
		for (int i=2;i<=tsq;++i)
		{
			int lc=LCA(stk[tp],seq[i]),lst=-1,len=quer[i-1][0];
			while (tp&&dep[stk[tp]]>dep[lc])
			{
				if (lst!=-1) tod[lst]=tof[tp+1],len-=tof[tp+1];
				lst=stk[tp];--tp;
			}
			if (stk[tp]^lc) stk[++tp]=lc;
			if (lst!=-1) tod[lst]=len;
			tof[tp]-=len;
			stk[++tp]=seq[i];tof[tp]=quer[i-1][1];
		}
		while (tp>1) tod[stk[tp]]=tof[tp],--tp;
		dfs2(nrt);
	}
	int pre[maxn],nxt[maxn],qv[maxn][2];
	void Process2()
	{
		for (int i=1;i<tsq;++i)
		{
			int t0=seq[i],t1=seq[i+1];
			nxt[t0]=t1;pre[t1]=t0;
			qv[t0][0]=quer[i][2];qv[t0][1]=quer[i][3];
		}
		int nowtt=tsq;
		while (nowtt>1)
		{
			int now=ord[nowtt];--nowtt;
			int t0=pre[now],t1=nxt[now];
			if (!t1)
			{
				int lc0=LCA(t0,now);
				nxt[t0]=0;
				tod[now]=lc0;dep2[now]=qv[t0][1];
				continue;
			}
			else if (!t0)
			{
				int lc1=LCA(t1,now);
				pre[t1]=0;
				tod[now]=lc1;dep2[now]=qv[now][0];
				continue;
			}
			int lc0=LCA(t0,now),lc1=LCA(t1,now);
			tod[now]=lc0;dep2[now]=qv[t0][1];
			qv[t0][1]=0ll+qv[t0][1]+qv[now][0]+qv[now][1]
			 -2ll*min(qv[t0][1],qv[now][0]);
			pre[t1]=t0;nxt[t0]=t1;
		}
		for (int i=2;i<=tsq;++i)
		 dep2[ord[i]]+=dep2[tod[ord[i]]];
	}
	int gtds(int x,int y){return 0ll+dep2[x]-2ll*dep2[LCA(x,y)]+dep2[y];}
}tr1,tr2;

int ask[maxm][2];

int main()
{
	for (i=2;i<maxn;++i)
	 Log[i]=Log[i>>1]+1;
	scanf("%d%d%d%d",&n,&K,&Q,&T);
	for (i=1;i<=n;++i)
	{
		scanf("%d",&t);
		tr1.add_edge(t,i);
	}
	for (i=1;i<=n;++i)
	{
		scanf("%d",&t);
		tr2.add_edge(t,i);
	}
	tr2.dfs_gt_seq(tr2.nrt);
	t=0;tr1.dfs1(tr1.nrt);t=0;tr2.dfs1(tr2.nrt);
	tr1.Process1();
	tr2.Process2();
	Flu();
	for (i=1;i<=T;++i)
	 scanf("%d%d",&ask[i][0],&ask[i][1]),Flu();
	for (i=1;i<=T;++i)
	{
		printf("%d %d\n",tr1.gtds(ask[i][0],ask[i][1]),tr2.gtds(ask[i][0],ask[i][1]));
	}
	Flu();
	return 0;
}
/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7

0 3 5 0
3 4 0 1
1 7
7 9
1 9

*/