#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<long long>
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct edge
{
int d1,d2;
ll d;
};
bool used[1000'001];
bool used2[1000'001];
vi query_list;
int used_cnt = 0;
int n,k,q,t;
struct tree
{
vi T[1000'001];
ll root_dist[1000'001];
int P[1000'001];
int jump[1000'001][20];
int dist[1000'001];
int root;
tree()
{
rep2(i,1,1000'000)
{
T[i] = {};
root_dist[i] = 0;
P[i] = i;
}
}
void dfs_dist(int v, int d)
{
dist[v] = d++;
forall(it,T[v])
{
dfs_dist(it,d);
}
}
void calc_jump(bool is_d = 1)
{
if(is_d) dfs_dist(root,0);
rep2(i,1,n) jump[i][0] = P[i];
rep2(bit,1,19)
{
rep2(i,1,n)
{
jump[i][bit] = jump[jump[i][bit-1]][bit-1];
}
}
}
int lca(int a, int b)
{
if(a == b) return a;
if(dist[a] < dist[b]) swap(a,b);
for(int bit = 19; bit >= 0; bit--)
{
if(dist[a] - (1 << bit) >= dist[b])
{
a = jump[a][bit];
}
}
if(a == b) return a;
for(int bit = 19; bit >= 0; bit--)
{
if(jump[a][bit] != jump[b][bit])
{
a = jump[a][bit];
b = jump[b][bit];
}
}
return jump[a][0];
}
void gen_set(int v)
{
if(used_cnt == k) return;
used_cnt++;
used[v] = 1;
forall(it,T[v])
{
gen_set(it);
}
}
void gen_query(int v)
{
if(used[v])
{
used2[v] = 1;
if(siz(query_list) == 0) query_list.pb(v);
else
{
int l = lca(query_list.back(),v);
used2[l] = 1;
cout << "? " << query_list.back() << " " << v << "\n";
query_list.pb(v);
}
}
forall(it,T[v])
{
gen_query(it);
}
}
void gen_new_tree(int v, int prev, int prev_ok, int d)
{
if(used[v])
{
dist[v] = d++;
if(prev_ok == -1)
{
P[v] = v;
}
else
{
P[v] = prev_ok;
}
prev_ok = v;
}
forall(it,T[v])
{
if(it != prev)
{
gen_new_tree(it,v,prev_ok,d);
}
}
}
void calc_tree(vi u, vector<edge> e)
{
int new_root = e[0].d1;
root = new_root;
rep2(i,1,n) if(P[i] != i) T[i].pb(P[i]);
rep2(i,1,n) used[i] = 0;
forall(it,u) used[it] = 1;
rep2(i,1,n) P[i] = i;
gen_new_tree(new_root,new_root,-1,0);
calc_jump(0);
rep2(i,1,n) root_dist[i] = 0;
vi lcas;
rep(i,siz(e))
{
lcas.pb(lca(e[i].d1,e[i].d2));
}
rep2(bit,1,31)
{
rep(i,siz(e))
{
auto it = e[i];
root_dist[it.d2] = (it.d - root_dist[it.d1] + 2 * root_dist[lcas[i]] + 15*(1LL << (ll)bit)) % (1LL << (ll)bit);
}
}
}
ll real_dist(int a, int b)
{
return root_dist[a] + root_dist[b] - 2 * root_dist[lca(a,b)];
}
};
tree T[2];
int main()
{
cin >> n >> k >> q >> t;
rep(d,2)
{
rep2(i,1,n)
{
int x;
cin >> x;
T[d].P[i] = x;
if(x != -1) T[d].T[x].pb(i);
else
{
T[d].root = i;
T[d].P[i] = i;
}
}
}
T[0].gen_set(T[0].root);
rep2(i,1,n)
{
if(used[i])
{
cout << i << " ";
}
}
cout << endl;
T[0].calc_jump();
T[1].calc_jump();
T[1].gen_query(T[1].root);
cout << "!" << endl;
vector<edge> e1;
vector<edge> e2;
rep(i,k-1)
{
int a,b,c,d;
cin >> a >> b >> c >> d;
int l1 = T[0].lca(query_list[i],query_list[i+1]);
if(l1 != query_list[i] && l1 != query_list[i+1])
{
e1.pb({query_list[i],l1,a});
e1.pb({l1,query_list[i+1],b});
}
else
{
e1.pb({query_list[i],query_list[i+1],a+b});
}
int l2 = T[1].lca(query_list[i],query_list[i+1]);
if(l2 != query_list[i] && l2 != query_list[i+1])
{
e2.pb({query_list[i],l2,c});
e2.pb({l2,query_list[i+1],d});
}
else
{
e2.pb({query_list[i],query_list[i+1],c+d});
}
}
vi u1;
vi u2;
rep2(i,1,n) if(used[i]) u1.pb(i);
rep2(i,1,n) if(used2[i]) u2.pb(i);
T[0].calc_tree(u1,e1);
T[1].calc_tree(u2,e2);
vector<pii> anses;
rep(qq,t)
{
int a,b;
cin >> a >> b;
anses.pb({T[0].real_dist(a,b),T[1].real_dist(a,b)});
}
forall(it,anses) cout << it.ff << " " << it.ss << "\n";
cout.flush();
}
