#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];
    void init(){
        d1[1][7] = d1[7][1] = 3;
        d2[1][7] = d2[7][1] = 5;
        d1[7][5] = d1[5][7] = 5;
        d2[7][5] = d2[5][7] = 3;
        d1[5][1] = d1[1][5] = 2;
        d2[5][1] = d2[1][5] = 8;
    }
}

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);
        }
    }
}

namespace sub2{
    bool is_virt[MAXN];
    vector<int> virt[MAXN];
    vector<int> list_virt;
    int ord[MAXN];
    int binlift[MAXN][21];
    int dep[MAXN];
    int t = 0;

    void dfs(int node){
        ord[node] = t++;
        for (int x : tree2[node]){
            dep[x] = dep[node]+1;
            binlift[x][0] = node;
            dfs(x);
        }
    }
    bool comp(int a, int b){
        return ord[a] < ord[b];
    }

    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];
            }
        }
    }
 
    int Kthabove(int node, int height){
        for (int i = 0; i <= 20; i++){
            if (height&(1<<i)){
                node = binlift[node][i];
            }
        }
        return node;
    }
 
    int lca(int u, int v){
        if (dep[u] > dep[v])
            swap(u, v);
        v = Kthabove(v, dep[v]-dep[u]);
        if (u == v)
            return u;
        for (int i = 20; i >= 0; i--){
            if (binlift[u][i] != binlift[v][i]){
                u = binlift[u][i], v = binlift[v][i];    
            }
        }
        return binlift[u][0];
    }

    int rt_virt;

    void dfs2(int node, int pa){
        int nx = pa;
        if (is_virt[node]){
            if (pa != 0){
                virt[pa].push_back(node);
            } else {
                rt_virt = node;
            }
            nx = node;
        }
        for (int x : tree2[node]){
            dfs2(x, nx);
        }
    }

    int sumlift2[MAXN][21], binlift2[MAXN][21], dep2[MAXN]; 

    void dfs3(int node){
        for (int x : virt[node]){
            dep2[x] = dep2[node]+1;
            binlift2[x][0] = node;
            dfs3(x);
        }
    }

    void genbin2(){
        for (int i = 1; i <= 20; i++){
            for (int j = 1; j <= N; j++){
                binlift2[j][i] = binlift2[binlift2[j][i-1]][i-1];
                sumlift2[j][i] = sumlift2[j][i-1]+sumlift2[binlift2[j][i-1]][i-1];
            }
        }
    }
 
    pair<int, int> Kthabove2(int node, int height){
        int ret = 0;
        for (int i = 0; i <= 20; i++){
            if (height&(1<<i)){
                ret += sumlift2[node][i];
                node = binlift2[node][i];
            }
        }
        return {node, ret};
    }
 
    int lca2(int u, int v){
        if (dep2[u] > dep2[v])
            swap(u, v);
        pair<int, int> ret = Kthabove2(v, dep2[v]-dep2[u]);
        v = ret.first;
        int sum = ret.second;
        if (u == v)
            return sum;
        for (int i = 20; i >= 0; i--){
            if (binlift2[u][i] != binlift2[v][i]){
                sum += sumlift2[u][i]+sumlift2[v][i];
                u = binlift2[u][i], v = binlift2[v][i];    
            }
        }
        return sum+sumlift2[u][0]+sumlift2[v][0];
    }

    void init(){
        dfs(rt2);
        genbin();

        vector<int> nodes;
        for (int i = 1; i <= K; i++){
            nodes.push_back(sub1::ord[i-1]);
        }
        sort(nodes.begin(), nodes.end(), comp);
        for (int x : nodes){
            is_virt[x] = true;
        }
        for (int i = 1; i < (int)nodes.size(); i++){
            int anc = lca(nodes[i-1], nodes[i]);
            is_virt[anc] = true;
        }
        dfs2(rt2, 0);
        dfs3(rt_virt);
        for (int i = 1; i <= N; i++){
            if (is_virt[i]){
                list_virt.push_back(i);
            }
        }
    }
}

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){
        cout << "1 5 7\n? 1 5\n? 1 7\n!\n";
        cout.flush();
        for (int i = 1; i <= Q; i++){
            int a, b, c, d; cin >> a >> b >> c >> d;
        }
        vector<pair<int, int> > input;
        for (int i= 1; i <= T; i++){
            int a, b; cin >> a >> b;
            input.push_back({a, b});
        }
        sample::init();
        for (int i = 1; i <= T; i++){
            cout << sample::d1[input[i-1].first][input[i-1].second] << " " << sample::d2[input[i-1].first][input[i-1].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 (i != K) cout << " ";
            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){
        sub1::dfs(rt);
        vector<pair<int, int> > ques;
        for (int i = 1; i <= K; i++){
            cout << sub1::ord[i-1];
            if (i != K) cout << " ";
            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];
        }
        sub2::init();
       
        for (pair<int, int> x : ques){
            cout << "? " << x.first << " " << x.second << "\n";
        }
        vector<pair<pair<int, int>, int> > ques2;
        for (int x : sub2::list_virt){
            for (int i = 0; i < (int)sub2::virt[x].size(); i += 2){
                ques2.push_back({{sub2::virt[x][i], sub2::virt[x][i+1]}, 1});
            }
            int sz = (int)sub2::virt[x].size();
            if (sz%2 == 1){
                int lst = sub2::virt[x].back();
                ques2.push_back({{sub2::binlift2[lst][0], lst}, 0});
            }
        }
        for (pair<pair<int, int>, int> x : ques2){
            cout << "? " << x.first.first << " " << x.first.second << "\n";
        }
        cout << "!" << endl;
        for (int i = 0; i < (int)ques.size(); i++){
            int a, b, c, d; cin >> a >> b >> c >> d;
            sub1::sumlift[ques[i].second][0] = b;
        }
        for (int i = 0; i < (int)ques2.size(); i++){
            int a, b, c, d; cin >> a >> b >> c >> d;
            if (ques2[i].second == 1){
                sub2::sumlift2[ques2[i].first.first][0] = c;
                sub2::sumlift2[ques2[i].first.second][0] = d;
            } else {
                sub2::sumlift2[ques2[i].first.second][0] = d;
            }
        }
        sub1::genbin();
        sub2::genbin2();
        /*
        for (int i = 1; i <= N; i++){
            cout << sub2::binlift2[i][0] << " ";
        }
        cout << "\n";
        for (int i = 1; i <= N; i++){
            cout << sub2::sumlift2[i][0] << " ";
        }
        cout << "\n";*/
        vector<pair<int, int> > input;
        for (int i = 1; i <= T; i++){
            int a, b; cin >> a >> b;
            input.push_back({a, b});
        }
        for (int i = 0; i < (int)input.size(); i++){
            cout << sub1::lca(input[i].first, input[i].second) << " " << sub2::lca2(input[i].first, input[i].second) << "\n";
        }
        cout.flush();
    }
}