//misaka and elaina will carry me to master
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <functional>
#include <numeric>
#include <set>
#include <array>
#include <queue>
#include <map>
#include <chrono>
#include <random>

#define ll long long
#define lb long double
#define sz(vec) ((int)(vec.size()))
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define kill(x, s) {int COND = x; if(COND){ cout << s << "\n"; return ; }}

#ifdef ONLINE_JUDGE
#define cerr while(0) cerr
#endif

const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
//const ll mod = (1 << (23)) * 119 +1, ll_max = 1e18;
const int MX = 1e6 +10, int_max = 0x3f3f3f3f;

struct {
  template<class T>
  operator T() {
    T x; std::cin >> x; return x;
  }
} in;

using namespace std;

struct hld{
	vector<int> dep, sz, par, head, tin, out;
	vector<vector<int>> adj;
	int n, ind;
	hld(){}
	hld(vector<pair<int, int>> edges, int rt = 1){
		n = sz(edges) + 1;
		ind = 0;
		dep = sz = par = head = tin = out = vector<int>(n+1, 0);
		adj = vector<vector<int>>(n+1);
		for(auto [a, b] : edges){
			adj[a].pb(b);
			adj[b].pb(a);
		}
		dfs(rt, 0);
		head[rt] = rt;
		dfs2(rt, 0);
	}
	void dfs(int x, int p){
		sz[x] = 1;
		dep[x] = dep[p] + 1;
		par[x] = p;
		for(auto &i : adj[x]){
			if(i == p) continue;
			dfs(i, x);
			sz[x] += sz[i];
			if(adj[x][0] == p || sz[i] > sz[adj[x][0]]) swap(adj[x][0], i);
		}
	}
	void dfs2(int x, int p){
		tin[x] = ind++;
		for(auto &i : adj[x]){
			if(i == p) continue;
			head[i] = (i == adj[x][0] ? head[x] : i);
			dfs2(i, x);
		}
		out[x] = ind;
	}
	int lca(int a, int b){
		while(head[a] != head[b]){
			if(dep[head[a]] > dep[head[b]]) swap(a, b);
			b = par[head[b]];
		}
		if(dep[a] > dep[b]) swap(a, b);
		return a;
	}
};

vector<int> par1, par2;
int n, k, q, t;


struct bad_tree{
	hld tr;
	vector<ll> dep;
	vector<vector<pair<int, ll>>> depend;
	vector<int> vis;
	//vector<pair<int, int>> depend[MX];
	//int vis[MX];
	//ll dep[MX];
	int exi;
	bad_tree(){}
	bad_tree(vector<int>& par){
		vis = vector<int>(n+1, 0);
		dep = vector<ll>(n+1, 0);
		depend = vector<vector<pair<int, ll>>>(n+1);
		exi = -1;
		vector<pair<int, int>> edges;
		int rt = 0;
		for(int i = 1; i<=n; i++){
			if(par[i] == -1){
				rt = i;
			}else{
				edges.pb(mp(i, par[i]));
			}
		}
		tr = hld(edges, rt);
	}
	void add(int a, int b, int c, int d){
		int l = tr.lca(a, b);
		if(exi == -1 || tr.dep[exi] > tr.dep[l]) exi = l;
		depend[a].pb(mp(l, c));
		depend[l].pb(mp(a, c));
		depend[b].pb(mp(l, d));
		depend[l].pb(mp(b, d));
	}
	void dfs(int u, int p, int w){
		cerr << u << " " << p << " " << w << "\n";
		if(vis[u]){
			assert(dep[u] == dep[p] + w);
			return ;
		}
		vis[u] = 1;
		dep[u] = dep[p] + w;
		for(auto [v, e] : depend[u]){
			if(tr.dep[v] > tr.dep[u]){
				dfs(v, u, e);
			}else{
				dfs(v, u, -e);
			}
		}
	}
	void norm(){
		dfs(exi, 0, 0);
		//for(int i = 1; i<=n; i++){
			//for(int j = 1; j<=n; j++){
				//if(vis[i] && vis[j]){
					//assert(vis[tr.lca(i, j)]); //:trust:
				//}
			//}
		//}
	}
	ll answer(int a, int b){
		return dep[a] + dep[b] - 2ll*dep[tr.lca(a, b)];
	}
};

namespace identical{
	hld tr;
	vector<int> tak;
	vector<int> adj[MX];
	int w[MX];
	ll dep[MX];
	vector<pair<int, int>> queries, edges;
	void dfs(int u, int p){
		if(sz(tak) < k) tak.pb(u);
		for(int v : adj[u]){
			if(v != p) dfs(v, u);
		}
	}
	void dfs2(int u, int p){
		dep[u] = dep[p] + w[u];
		for(int v : adj[u]){
			if(v != p)
				dfs2(v, u);
		}
	}	
	void solve(){
		vector<int> par = par1;
		int rt = 0;
		for(int i = 1; i<=n; i++){
			if(par[i] != -1){
				adj[par[i]].pb(i);
				adj[i].pb(par[i]);
				edges.pb(mp(par[i], i));
			}else{
				rt = i;
			}
		}
		assert(rt != 0);
		dfs(rt, 0);
		assert(sz(tak) == k);
		assert(tak[0] == rt);
		assert(k - 1 == q);
		for(int i = 0; i<k; i++){
			cout << tak[i];
			if(i == k-1) cout << endl;
			else cout << " ";
		}
		for(int i = 1; i<k; i++){
			cout << "? " << tak[i] << " " << par1[tak[i]] << "\n";
		}
		cout << "!" << endl;
		cout.flush();
		for(int i = 1; i<k; i++){
			int a = in, b = in, c = in, d = in;
			//assert(b == 0 && d == 0);
			//assert(a == c);
			w[tak[i]] = a;
		}
		for(int i = 0; i<t; i++){
			int a = in, b = in;
			queries.pb(mp(a, b));
		}
		dfs2(rt, 0);
		tr = hld(edges, rt);
		for(int i = 0; i<t; i++){
			auto [u, v] = queries[i];
			ll ans = dep[u] + dep[v] - 2ll*dep[tr.lca(u, v)];
			cout << ans << " " << ans << "\n";;
		}
		cout.flush();
	}
}

namespace big_query{
	bad_tree A, B;

	bool cmp1(int a, int b){
		return A.tr.tin[a] < A.tr.tin[b];
	}

	bool cmp2(int a, int b){
		return B.tr.tin[a] < B.tr.tin[b];
	}
	void solve(){
		A = bad_tree(par1);
		B = bad_tree(par2);
		vector<int> rel1(k), rel2(k);
		iota(all(rel1), 1);
		iota(all(rel2), 1);
		sort(all(rel1), cmp1);
		sort(all(rel2), cmp2);
		for(int i = 0; i<k; i++){
			cout << i+1;
			if(i == k-1) cout << endl;
			else cout << " ";
		}

		for(int i =1 ; i<k; i++){
			cout << "? " << rel1[i-1] << " " << rel1[i] << endl;
		}
		for(int i =1 ; i<k; i++){
			cout << "? " << rel2[i-1] << " " << rel2[i] << endl;
		}
		cout << "!" << endl;
		for(int i = 0; i<q; i++){
			int a= in, b = in, c = in, d = in;
			int u = (i >= k-1) ? rel2[i- (k-1)] : rel1[i];
			int v = (i >= k-1) ? rel2[i- (k-1) +1] : rel1[i +1];
			cerr << u << " " << v << " " << a << " " << b << " " << c << " " << d << "\n";
			A.add(u, v, a, b);
			B.add(u, v, c, d);
		}
		A.norm();
		B.norm();
		vector<pair<int, int>> queries;
		for(int i = 0; i<t; i++){
			int a = in, b = in;
			queries.pb(mp(a, b));
		}
		for(int i = 0; i<t; i++){
			auto [a, b] = queries[i];
			cout << A.answer(a, b) << " "<< B.answer(a, b) << endl;
		}
		
	}
}



void solve(){
	n = in, k = in, q =in, t = in;
	par1 = par2 = vector<int>(n+1, 0);
	for(int i = 1; i<=n; i++){
		par1[i] = in;
	}
	for(int i = 1; i<=n; i++){
		par2[i] = in;
	}
	if(par1 == par2){
		identical::solve();
	}else if(q == 2*k -2){
		big_query::solve();
	}else{
		int ans[2][10][10];
		memset(ans, 0, sizeof(ans));
		cout << "1 5 7" << endl;
		cout << "? 1 5" << endl;
		cout << "? 1 7" << endl;
		cout << "!" << endl;
		vector<pair<int, int>> queries;
		for(int i = 0; i<k-1; i++){
			int a = in, b = in, c = in, d = in;
		}			
	
		for(int i = 0; i<t; i++){
			int a = in, b = in;
			queries.pb(mp(a, b));
		}	
		ans[0][1][5] = ans[0][5][1] = 2;
		ans[0][1][7] = ans[0][7][1] = 3;
		ans[0][5][7] = ans[0][7][5] = 5;
		ans[1][1][5] = ans[1][5][1] = 8;
		ans[1][5][7] = ans[1][7][5] = 3;
		ans[1][7][1] = ans[1][1][7] = 5;
		for(auto [a, b] : queries){
			cout << ans[0][a][b] << " " << ans[1][a][b] << endl;
		}
	}
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);

  int T = 1;
  //cin >> T;
  for(int i = 1; i<=T; i++){
		solve();
	}
  return 0;
}