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

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

const int MAXN = 5000+10;

int N, K, Q, T;

vector<int> tree[MAXN], tree2[MAXN];
int par[MAXN], par2[MAXN];
int rt, rt2;

namespace sample{
    int d1[12][12], d2[12][12];
    const int INF = 1e9;
    void init(){
        d1[2][1] = 3, d1[2][3] = 1, d1[1][4] = 7, d1[1][5] = 2, d1[1][7] = 3, d1[4][8] = 5, d1[5][6] = 1, d1[5][9] = 2;
        d2[7][5] = 3, d2[7][9] = 1, d2[9][1] = 4, d2[5][3] = 7, d2[5][4] = 9, d2[4][2] = 1, d2[3][6] = 2, d2[3][8] = 5;
        for (int i = 1; i <= N ;i++){
            for (int j = 1; j <= N; j++){
                d1[i][j] = max(d1[i][j], d1[j][i]);
                d2[i][j] = max(d2[i][j], d2[j][i]);
            }
        }
        for (int i =1; i <= N ;i++){
            for (int j = 1; j <= N; j++){
                if (d1[i][j] == 0) d1[i][j] = INF;
                if (d2[i][j] == 0) d2[i][j] = INF;
            }
        }
        for (int i = 1; i <= N; i++) d1[i][i] = d2[i][i] = 0;
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                for (int k = 1; k <= N; k++){
                    d1[j][k] = min(d1[j][k], d1[j][i]+d1[i][k]);
                    d2[j][k] = min(d2[j][k], d2[j][i]+d2[i][k]);
                }
            }
        }
    }
}

namespace sub1{
    int binlift[MAXN][21], sumlift[MAXN][21], dep[MAXN];
    vector<int> ord;
    void genbin(){
        for (int i = 1; i <= 20; i++){
            for (int j = 1; j <= N; j++){
                binlift[j][i] = binlift[binlift[j][i-1]][i-1];
                sumlift[j][i] = sumlift[j][i-1]+sumlift[binlift[j][i-1]][i-1];
            }
        }
    }
 
    pair<int, int> Kthabove(int node, int height){
        int ret = 0;
        for (int i = 0; i <= 20; i++){
            if (height&(1<<i)){
                ret += sumlift[node][i];
                node = binlift[node][i];
            }
        }
        return {node, ret};
    }
 
    int lca(int u, int v){
        if (dep[u] > dep[v])
            swap(u, v);
        pair<int, int> ret = Kthabove(v, dep[v]-dep[u]);
        v = ret.first;
        int sum = ret.second;
        if (u == v)
            return sum;
        for (int i = 20; i >= 0; i--){
            if (binlift[u][i] != binlift[v][i]){
                sum += sumlift[u][i]+sumlift[v][i];
                u = binlift[u][i], v = binlift[v][i];    
            }
        }
        return sum+sumlift[u][0]+sumlift[v][0];
    }

    void dfs(int node){
        ord.push_back(node);
        for (int x : tree[node]){
            dep[x] = dep[node]+1;
            dfs(x);
        }
    }
}

int main(){
    //fastIO();
    cin >> N >> K >> Q >> T;
    for (int i = 1; i <= N; i++){
        int p; cin >> p;
        par[i] = p;
        if (p == -1){
            rt = i;
        } else {
            tree[p].push_back(i);
        }
    }
    for (int i = 1; i <= N; i++){
        int p; cin >> p;
        par2[i] = p;
        if (p == -1){
            rt2 =i;
        } else {
            tree2[p].push_back(i);
        }
    }
    if (N == 9){
        for (int i = 1; i <= K; i++) cout << i << " ";
        cout << "\n";
        cout.flush();
        for (int i = 1; i <= Q; i++){
            cout << "? " << i << " " << i << "\n";
        }
        cout << "!\n";
        cout.flush();
        for (int i = 1; i <= Q; i++){
            int a, b, c, d; cin >> a >> b >> c >> d;
        }
        sample::init();
        vector<pair<int, int> > ans;
        for (int i = 1; i <= T; i++){
            int a, b; cin >> a >> b;
            ans.push_back({sample::d1[a][b], sample::d2[a][b]});
        }
        for (pair<int, int> x : ans){
            cout << x.first << " " << x.second << "\n";
        }
        cout.flush();
    } else if (N == 500000 && Q == K-1){
        sub1::dfs(rt);
        vector<pair<int, int> > ques;
        for (int i = 1; i <= K; i++){
            cout << sub1::ord[i-1] << " ";
            if (par[sub1::ord[i-1]] != -1){
                ques.push_back({par[sub1::ord[i-1]], sub1::ord[i-1]});
            }
        }
        cout << "\n";
        cout.flush();
        for (int i = 1; i <= N; i++){
            sub1::binlift[i][0] = par[i];
        }
        for (pair<int, int> x : ques){
            cout << "? " << x.first << " " << x.second << "\n";
        }
        cout << "!\n";
        cout.flush();
        for (int i = 1; i <= Q; i++){
            int a, b, c, d; cin >> a >> b >> c >> d;
            sub1::sumlift[ques[i-1].second][0] = b;
        }
        sub1::genbin();
        vector<pair<int, int> > input;
        for (int i = 1; i <= T; i++){
            int u, v; cin >> u >> v;
            input.push_back({u, v});
        }
        for (pair<int, int> x : input){
            int val = sub1::lca(x.first, x.second);
            cout << val << " " << val << "\n";
        }
        cout.flush();
    } else if (N == 500000 && Q == 2*K-2){
        
    }
}