// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = - f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 1e6 + 10;
int n, k, q, t;
struct Tree {
	int fa[N], rt, dfn[N], nfd[N], dfscnt, sz[N], son[N], dep[N], top[N], dis[N];
	vector <int> v[N];
	void dfs(int x) {
		dep[x] = dep[fa[x]] + 1;
		sz[x] = 1;
		for (int i: v[x]) {
			dfs(i);
			sz[x] += sz[i];
			if (sz[i] > sz[son[x]]) son[x] = i;
		}
		if (son[x]) v[x].erase(find(all(v[x]), son[x])), v[x].insert(v[x].begin(), son[x]);
	}
	void dfs2(int x, int tt) {
		top[x] = tt;
		nfd[dfn[x] = ++dfscnt] = x;
		for (int i: v[x]) dfs2(i, i == v[x].front() ? tt : i);
	}
	void init() {
		F(i, 1, n) {
			cin >> fa[i];
			if (!~fa[i]) fa[i] = 0, rt = i;
			else v[fa[i]].push_back(i);
		}
		dfs(rt), dfs2(rt, rt);
	}
	int lca(int x, int y) {
		while (top[x] != top[y]) {
			if (dep[top[x]] > dep[top[y]]) swap(x, y);
			y = fa[top[y]];
		}
		return dep[x] < dep[y] ? x : y;
	}
	int query(int x, int y) {
		return dis[x] - dis[lca(x, y)] * 2 + dis[y];
	}
} T1, T2;
int val[N], an[N];
vector <pair <int, int>> v[N], vv[N];
void dfs(int x, int g) {
	T2.dis[x] = g;
	// debug << x << " " << T2.dis[x] << endl;
	for (auto [i, j]: vv[x]) dfs(i, g + j);
}
signed main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> k >> q >> t;
	T1.init(), T2.init();
	vector <int> g;
	F(i, 1, k) g.push_back(T1.nfd[i]);//, debug << T1.nfd[i] << endl;
	// debug << T1.rt << endl;
	sort(all(g), [&] (int x, int y) {
		return T2.dfn[x] < T2.dfn[y];
	});
	for (int i: g) cout << i << " "; cout << endl;
	F(i, 0, SZ(g) - 1) cout << "? " << g[i] << " " << g[i + 1] << '\n';
	cout << "!" << endl;
	// set <int> s;
	stack <int> s;
	s.push(g[0]);
	F(i, 0, SZ(g) - 1) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		int k1 = T1.lca(g[i], g[i + 1]);
		int k2 = T2.lca(g[i], g[i + 1]);
		// debug << k1 << " " << k2 << endl;
		v[k1].emplace_back(g[i], a);
		v[g[i]].emplace_back(k1, - a);
		v[k1].emplace_back(g[i + 1], b);
		v[g[i + 1]].emplace_back(k1, - b);
		// if (k2 == )
		an[g[i + 1]] = k2;
		val[g[i + 1]] = d;
		int lst = 0;
		while (s.size() && T2.dep[s.top()] > T2.dep[k2]) c -= val[lst], lst = s.top(), s.pop();
		if (s.empty() || s.top() != k2) {
			assert(lst);
			if (s.size()) {
				an[k2] = s.top();
				val[k2] = val[lst] - c;
			}
			an[lst] = k2;
			val[lst] = c;
			s.emplace(k2);
		}
		s.push(g[i + 1]);
		// s[g[i + 1]] = d;
		// an[g[i + 1]] = k2;
		// if (!s[g[i]]) {
		// 	s[g[i]] = d;
		// 	an[g[i]] = d;
		// } else {
		// 	if (T2.dep[an[g[i]]] < T2.dep[g[i]]) {
		// 	}
		// }
	}
	queue <int> q;
	// int rt = T1.nfd[1];
	T1.dis[T1.rt] = 1;
	q.push(T1.rt);
	while (q.size()) {
		int x = q.front(); q.pop();
		// debug << x << " " << T1.dis[x] << endl;
		for (auto [i, j]: v[x])
			if (!T1.dis[i]) {
				// debug << i << " " << x << " " << j << endl;
				T1.dis[i] = T1.dis[x] + j;
				q.push(i);
			}
	}
	// for (int i: g) cout << T1.dis[i] << " "; debug << endl;
	while (s.size() > 1) s.pop();
	F(i, 1, n)
		if (an[i]) vv[an[i]].emplace_back(i, val[i]);
	dfs(s.top(), 0);
	F(i, 1, t) {
		int p, q; cin >> p >> q;
		// int k1 = T1.lca(p, q), k2 = T2.lca(p, q);
		// cout << T1.query(p, k1) << " " << T1.query(q, k1) << " " << T2.query(p, k2) << " " << T2.query()
		cout << T1.query(p, q) << " " << T2.query(p, q) << '\n';
	}
	cout << endl;
	return 0;
}
/* why?
*/