#include <bits/stdc++.h>
using namespace std;

template<class Fun>
class y_combinator_result {
	Fun fun;
public:
	template<class T>
	explicit y_combinator_result(T &&_fun) : fun(forward<T>(_fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun(ref(*this), forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}

struct heavy_light_decomposition {
	vector<int> par, dep, hed, tin;

	heavy_light_decomposition(int R, vector<vector<int>> T) {
		int n = T.size(), time = 0;
		par.resize(n), dep.resize(n);
		hed.resize(n), tin.resize(n);
		par[R] = -1, dep[R] = 0, hed[R] = R;

		y_combinator([&](auto self, int u) -> int {
			int sub = 1, mxs = 0;
			for (int &v : T[u]) {
				par[v] = u;
				dep[v] = dep[u] + 1;
				int t = self(v);
				sub += t;
				if (mxs < t) {
					mxs = t;
					swap(T[u].front(), v);
				}
			}
			return sub;
		})(R);

		y_combinator([&](auto self, int u) -> void {
			tin[u] = time++;
			for (int v : T[u]) {
				hed[v] = v == T[u].front() ? hed[u] : v;
				self(v);
			}
		})(R);

		// for (int u = 0; u < n; u++) 
		// 	cerr << u << " : " << par[u] << ' ' << dep[u] << ' ' << hed[u] << ' ' << tin[u] << '\n';
		// cerr << "-------------------------\n";
	}

	int lowest_common_ancestor(int u, int v) {
		for (; hed[u] != hed[v]; u = par[hed[u]])
			if (dep[hed[u]] < dep[hed[v]])
				swap(u, v);
		return dep[u] < dep[v] ? u : v;
	}
};

struct virtual_tree {
	int n;
	heavy_light_decomposition &hld;
	pair<int, int> mnd = make_pair(1e9, -1);
	vector<vector<pair<int, int>>> vir;
	vector<int> dis;

	virtual_tree(int _n, heavy_light_decomposition &_hld) : n(_n), hld(_hld) {
		vir.resize(n);
		dis.resize(n);
	}

	void add_virtual_edge(int u, int v, int du, int dv) {
		int lca = hld.lowest_common_ancestor(u, v);
		// cerr << "lca of " << u << " and " << v << " = " << lca << '\n';
		mnd = min(mnd, make_pair(hld.dep[lca], lca));
		if (u != lca) {
			vir[lca].emplace_back(u, du);
			vir[u].emplace_back(lca, -du);
		}
		if (v != lca) {
			vir[lca].emplace_back(v, dv);
			vir[v].emplace_back(lca, -dv);
		}
	}

	void build_virtual_tree() {
		queue<int> que;
		vector<bool> vis(n, false);
		que.push(mnd.second);
		while (!que.empty()) {
			int u = que.front(); que.pop();
			for (auto [v, w] : vir[u]) {
				dis[v] = dis[u] + w;
				if (!vis[v]) {
					vis[v] = true;
					que.push(v);
				}
			}
		}
	}

	int query_distance(int u, int v) { return dis[u] + dis[v] - 2 * dis[hld.lowest_common_ancestor(u, v)]; }
};

int main() {
	int N, K, Q, T;
	cin >> N >> K >> Q >> T;
	int R1 = -1, R2 = -1;
	vector<vector<int>> T1(N), T2(N);
	for (int i = 0; i < N; i++) {
		int p;
		cin >> p;
		if (p == -1)
			R1 = i;
		else 
			T1[p - 1].push_back(i);
	}
	for (int i = 0; i < N; i++) {
		int p;
		cin >> p;
		if (p == -1)
			R2 = i;
		else 
			T2[p - 1].push_back(i);
	}

	heavy_light_decomposition hld1(R1, T1), hld2(R2, T2);
	virtual_tree vit1(N, hld1), vit2(N, hld2);

	vector<int> X;
	X.reserve(K);
	queue<int> que;
	que.push(R1);
	while (X.size() < K) {
		int u = que.front(); que.pop();
		X.push_back(u);
		for (int v : T1[u])
			que.push(v);
	}

	sort(X.begin(), X.end(), [&hld2](int u, int v) {
		return hld2.tin[u] < hld2.tin[v];
	});

	for (int i = 0; i < K; i++)
		cout << X[i] + 1 << ' ';
	cout << endl; cout.flush();
	for (int i = 0; i < K - 1; i++) 
		cout << "? " << X[i] + 1 << ' ' << X[i + 1] + 1 << '\n';
	cout << '!' << endl;
	cout.flush();

	for (int i = 0; i < K - 1; i++) {
		int f, g, p, q;
		cin >> f >> g >> p >> q;
		vit1.add_virtual_edge(X[i], X[i + 1], f, g);
		vit2.add_virtual_edge(X[i], X[i + 1], p, q);
	}

	vit1.build_virtual_tree();
	vit2.build_virtual_tree();

	vector<pair<int, int>> ans(T);
	for (int t = 0; t < T; t++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		ans[t] = {vit1.query_distance(u, v), vit2.query_distance(u, v)};
	}
	for (int t = 0; t < T; t++)
		cout << ans[t].first << ' ' << ans[t].second << '\n';
	cout.flush();
}

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

10 0 0 1
0 3 13 5
*/