#include <bits/stdc++.h>
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
template<typename T>void print(T x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
vector <int> S;
int lg[1000005];
bool cho[1000005];//Is a node chosen
int rt1,rt2,n,k,q,t;
int dfn[1000005],Times;
int dep1[1000005],dep2[1000005];
map<int,int>M1[1000005],M2[1000005];
int f1[1000005][21],f2[1000005][21];
vector <int> G1[1000005],G2[1000005];
vector <PII> V1[1000005],V2[1000005];
vector <int> Inc1[1000005],Inc2[1000005];
int Ans1[1000005],Ans2[1000005],Ans3[1000005],Ans4[1000005]; 
int cnt,Asku[1000005],Askv[1000005],AskA1[1000005],AskA2[1000005];//u,v and ancestor on each tree
void dfs1(int u,int fa)
{
	f1[u][0]=fa; dep1[u]=dep1[fa]+1;
	for(int i=1;i<=lg[dep1[u]];i++) f1[u][i]=f1[f1[u][i-1]][i-1];
	if((int)S.size()<k) S.push_back(u),cho[u]=true;
	for(int i=0;i<(int)G1[u].size();i++)
	{
		int v=G1[u][i];
		if(v==fa) continue;
		dfs1(v,u);
	}
}
int LCA1(int x,int y)
{
	if(dep1[x]<dep1[y]) swap(x,y);
	for(int i=lg[dep1[x]-dep1[y]];~i;i--) if(dep1[f1[x][i]]>=dep1[y]) x=f1[x][i];
	if(x==y) return x;
	for(int i=lg[dep1[x]];~i;i--) if(f1[x][i]!=f1[y][i]) x=f1[x][i],y=f1[y][i];
	return f1[x][0];
}
int lst=-1;
void dfs2(int u,int fa)
{
	dfn[u]=++Times;
	f2[u][0]=fa; dep2[u]=dep2[fa]+1;
	if(cho[u])
	{
		if(~lst)
		{
			putchar('?');putchar(' ');
			print(u);putchar(' ');
			print(lst);putchar('\n');
			Asku[++cnt]=u; Askv[cnt]=lst; AskA1[cnt]=LCA1(u,lst);
			Inc1[u].push_back(cnt);
			if(lst!=u) Inc1[lst].push_back(cnt);
			if(AskA1[cnt]!=u&&AskA1[cnt]!=lst) Inc1[AskA1[cnt]].push_back(cnt);
		}
		lst=u;
	}
	for(int i=1;i<=lg[dep2[u]];i++) f2[u][i]=f2[f2[u][i-1]][i-1];
	for(int i=0;i<(int)G2[u].size();i++)
	{
		int v=G2[u][i];
		if(v==fa) continue;
		dfs2(v,u);
	}
}
int LCA2(int x,int y)
{
	if(dep2[x]<dep2[y]) swap(x,y);
	for(int i=lg[dep2[x]-dep2[y]];~i;i--) if(dep2[f2[x][i]]>=dep2[y]) x=f2[x][i];
	if(x==y) return x;
	for(int i=lg[dep2[x]];~i;i--) if(f2[x][i]!=f2[y][i]) x=f2[x][i],y=f2[y][i];
	return f2[x][0];
}
int dis3[1000005],dis4[1000005];
bool vis3[1000005],vis4[10000005];
int cmp(int x,int y){return dfn[x]<dfn[y];}
int main() {
//	freopen("InterOut","r",stdin);
//	freopen("MyOut","w",stdout);
	read(n);read(k);read(q);read(t);
	for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1,fa;i<=n;i++)
	{
		read(fa);
		if(fa==-1) rt1=i;
		else G1[fa].push_back(i);	
	}
	for(int i=1,fa;i<=n;i++)
	{
		read(fa);
		if(fa==-1) rt2=i;
		else G2[fa].push_back(i);
	}
//	fclose(stdin);
	dfs1(rt1,0);
	for(int i=0;i<(int)S.size();i++) print(S[i]),putchar(' ');puts("");
	dfs2(rt2,0);//建倍增表，顺便选点和得到询问
	assert(cnt<=q);
	for(int i=1;i<=cnt;i++)
	{
		AskA2[i]=LCA2(Asku[i],Askv[i]);
		Inc2[AskA2[i]].push_back(i);	
		if(Asku[i]!=AskA2[i]) Inc2[Asku[i]].push_back(i);
		if(Askv[i]!=AskA2[i]) Inc2[Askv[i]].push_back(i);
	}
	puts("!");
	fflush(stdout);
//	fclose(stdout);
	int rt4=LCA2(S[0],S[1]);
	for(int i=2;i<(int)S.size();i++) rt4=LCA2(rt4,S[i]);
	for(int i=1;i<=cnt;i++) read(Ans1[i]),read(Ans2[i]),read(Ans3[i]),read(Ans4[i]);
	queue<int>Q;
	Q.push(rt4);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		if(vis4[u]) continue; vis4[u]=true;
		for(int i=0;i<(int)Inc2[u].size();i++)
		{
			int id=Inc2[u][i];
			if(AskA2[id]==u)
			{
				dis4[Asku[id]]=dis4[u]+Ans3[id];
				dis4[Askv[id]]=dis4[u]+Ans4[id];
				if(!vis4[Asku[id]]) Q.push(Asku[id]);
				if(!vis4[Askv[id]]) Q.push(Askv[id]);	
			}
			else
			{
				if(Asku[id]==u) dis4[AskA2[id]]=dis4[u]-Ans3[id];
				if(Askv[id]==u) dis4[AskA2[id]]=dis4[u]-Ans4[id];
				if(!vis4[AskA2[id]]) Q.push(AskA2[id]);
			}

		}
	}
	Q.push(rt1);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		if(vis3[u]) continue; vis3[u]=true;
		for(int i=0;i<(int)Inc1[u].size();i++)
		{
			int id=Inc1[u][i];
			if(AskA1[id]==u)
			{
				dis3[Asku[id]]=dis3[u]+Ans1[id];
				dis3[Askv[id]]=dis3[u]+Ans2[id];
				if(!vis3[Asku[id]]) Q.push(Asku[id]);
				if(!vis3[Askv[id]]) Q.push(Askv[id]);	
			}
			else
			{
				if(Asku[id]==u) dis3[AskA1[id]]=dis3[u]-Ans1[id];
				if(Askv[id]==u) dis3[AskA1[id]]=dis3[u]-Ans2[id];
				if(!vis3[AskA1[id]]) Q.push(AskA1[id]);
			}

		}
	}
//	freopen("MyOut","a",stdout);
	for(int i=1,a,b;i<=t;i++)
	{
		read(a);read(b);
		int A1=LCA1(a,b),A2=LCA2(a,b);
		print(dis3[a]+dis3[b]-dis3[A1]*2);putchar(' ');
		print(dis4[a]+dis4[b]-dis4[A2]*2);putchar('\n');
	} 
	fflush(stdout);
	return 0;
}
/*
先把思路写在这里，感觉是大工程
在第一棵树上dfs取最先得到的k的点
然后在第二课树上建出这k个点的虚树直接挨着询问每条边
这k-1个询问中必定有询问在第一棵树上有LCA为根，因为至少我选了根
那么从根开始可以得到一些点的深度
然后继续把涉及这些点的询问全部拎出来就可以得到每个点的深度（大概）

肯定写复杂了！ 

9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7

0 10 1 0
3 0 5 13
*/