#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ff first
#define ss second
using namespace std;
int n, q, k, t;
int roots[2];
vector<int>child[500005][2];
vector<int>childReal[500005][2];
vector<int>chosen;
bool isChosen[500005];
int lca[500005][20][2];
int distancia[500005][20][2];
int deep[5000005][2];


void bfs(int s, int tri = 0){
	queue<pair<int, int > >cola; // node, deep
	cola.push({s, 0});
	while(!cola.empty() and chosen.size() < k){
		auto cur = cola.front();
		cola.pop();
		chosen.pb(cur.ff);
		deep[cur.ff][tri] = cur.ss;
		isChosen[cur.ff] = true;
		for(int i = 0 ; i < child[cur.ff][tri].size() ; i ++){
			lca[child[cur.ff][tri][i]][0][tri] = cur.ff;
			cola.push({child[cur.ff][tri][i], cur.ss + 1});
		}
	}	
}


int getDist(int a, int b, int tri){
	if(deep[a][tri] < deep[b][tri])swap(a, b);
	int dd = deep[a][tri] - deep[b][tri];
	int ans = 0;
	for(int i = 19 ; i >= 0 ; i --){
		if(dd & (1<<i)){
			ans += distancia[a][i][tri];
			a = lca[a][i][tri];
		}
	}
	if(a == b)return ans;
	for(int i = 19 ; i >= 0 ; i --){
		if(lca[a][i][tri] != lca[b][i][tri]){
			ans += distancia[a][i][tri];
			ans += distancia[b][i][tri];
			a = lca[a][i][tri];
			b = lca[b][i][tri];
		}
	}
	ans += distancia[a][0][tri] + distancia[b][0][tri];
	return ans;
	
	
}
struct estado{
	int node;
	int deep;
	int arbol;
};

void bfs2(int s1, int s2){
	queue<estado >cola; // node, deep
	cola.push({s1, 0, 0});
	cola.push({s2, 0, 1});
	while(!cola.empty() and chosen.size() < k){
		auto cur = cola.front();
		int nd = cur.node;
		int prof = cur.deep;
		int tri = cur.arbol;
		cola.pop();
		if(!isChosen[nd]){
			chosen.pb(nd);
			isChosen[nd] = true;
		}
		for(int i = 0 ; i < child[nd][tri].size() ; i ++){
			lca[child[nd][tri][i]][0][tri] = nd;
			cola.push({child[nd][tri][i], prof + 1, tri});
		}
	}	
}

void dfs(int nd, int tri, int last, int dip){
	if(last != -1 and isChosen[nd]){
		childReal[last][tri].pb(nd);
		lca[nd][0][tri] = last;
	}
	if(isChosen[nd]){
		last = nd;
		deep[nd][tri] = dip;
		dip ++ ;
	}
	
	for(int i = 0 ; i < child[nd][tri].size() ; i ++){
		int &nx = child[nd][tri][i];
		dfs(nx, tri, last, dip);
	}
}

void getChildReal(){
	dfs(roots[0], 0, -1, 0);
	dfs(roots[1], 1, -1, 0);
	
}

int main(){
	ios::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	/*
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	* */
	cin >> n >> k >> q >> t;
	memset(isChosen, false, sizeof isChosen);
	int temp;
	for(int i = 1 ; i <= n ; i ++){
		cin >> temp;
		if(temp == -1)roots[0] = i;
		else child[temp][0].pb(i);
	}
	for(int i = 1 ; i <= n ; i ++){
		cin >> temp;
		if(temp == -1)roots[1] = i;
		else child[temp][1].pb(i);
	}
	if(q == k-1){
		bfs(roots[0]);
		for(auto i : chosen)cout << i << " ";
		cout << endl;	
		vector<int>questions;	
	
		for(int i = 0 ; i < k ; i ++){
			for(int j = 0 ; j < child[chosen[i]][0].size() ; j ++){
				if(isChosen[child[chosen[i]][0][j]]){
					questions.pb(child[chosen[i]][0][j]);
				}
			}
		}
		for(int i = 0 ; i < questions.size() ; i ++){
			cout << "? " << questions[i] << " " << lca[questions[i]][0][0] << endl;
		}
		cout << "!" << endl;
		for(int i = 0 ; i < questions.size() ; i ++){
			int a, b;
			cin >> a >> b >> a >> b;
			distancia[questions[i]][0][0] = a;
		}
		lca[roots[0]][0][0] = roots[0];
		distancia[roots[0]][0][0] = 0;
		for(int x = 1 ; x < 20 ; x ++){
			for(auto i : chosen){
				lca[i][x][0] = lca[lca[i][x-1][0]][x-1][0];
				distancia[i][x][0] = distancia[lca[i][x-1][0]][x-1][0] + distancia[i][x-1][0];
				//lca[i][x][1] = lca[lca[i][x-1][1]][x-1][1];
			}
		}
		vector<pair<int, int> > queries;
		for(int i = 0 ; i < t ; i ++){
			int a, b;
			cin >> a >> b;
			queries.pb({a, b});
		}
		for(int i = 0 ;  i < t ; i ++){
			cout << getDist(queries[i].ff, queries[i].ss, 0) << " " << getDist(queries[i].ff, queries[i].ss, 0) << "\n";
		}
		cout << endl;
	}else{
		vector<int>questions2;
		bfs2(roots[0], roots[1]);
		for(auto i : chosen) cout << i << " ";
		cout << endl;
		vector<pair<int, int > >q1, q2; // child, parent
		getChildReal();
		for(int i = 0 ; i < k ; i ++){
			for(int j = 0 ; j < childReal[chosen[i]][0].size() ; j ++){
				q1.pb({childReal[chosen[i]][0][j], chosen[i]});
			}
		}
		for(int i = 0 ; i < k ; i ++){
			for(int j = 0 ; j < childReal[chosen[i]][1].size() ; j ++){
				q2.pb({childReal[chosen[i]][1][j], chosen[i]});
			}
		}
		for(int i = 0 ; i < q1.size() ; i ++){
			cout << "? " << q1[i].ff << " " << q1[i].ss << endl;
		}
		for(int i = 0 ; i < q2.size() ; i ++){
			cout << "? " << q2[i].ff << " " << q2[i].ss << endl;
		}
		cout << "!" << endl;
		for(int i = 0 ; i < q1.size() ; i ++){
			int a, b;
			cin >> a >> b;
			distancia[q1[i].ff][0][0] = a;
			cin >> a >> b;
		}
		for(int i = 0 ; i < q2.size() ; i ++){
			int a, b;
			cin >> a >> b >> a >> b;
			distancia[q2[i].ff][0][1] = a;
		}
		lca[roots[0]][0][0] = roots[0];
		distancia[roots[0]][0][0] = 0;
		lca[roots[1]][0][1] = roots[1];
		distancia[roots[1]][0][1] = 0;
		for(int x = 1 ; x < 20 ; x ++){
			for(auto i : chosen){
				lca[i][x][0] = lca[lca[i][x-1][0]][x-1][0];
				distancia[i][x][0] = distancia[lca[i][x-1][0]][x-1][0] + distancia[i][x-1][0];
				lca[i][x][1] = lca[lca[i][x-1][1]][x-1][1];
				distancia[i][x][1] = distancia[lca[i][x-1][1]][x-1][1] + distancia[i][x-1][1];
			}
		}
		vector<pair<int, int> > queries;
		for(int i = 0 ; i < t ; i ++){
			int a, b;
			cin >> a >> b;
			queries.pb({a, b});
		}
		for(int i = 0 ;  i < t ; i ++){
			cout << getDist(queries[i].ff, queries[i].ss, 0) << " " << getDist(queries[i].ff, queries[i].ss, 1) << "\n";
		}
		cout << endl;
	}
	int ready;
	//~ cin >> ready;
	return 0;
}