#include
using namespace std;
class node{
public:
int data ;
nodeleft;
noderight;
node( int d){
data = d;
left = NULL;
right = NULL;
}
};
nodebuilttree(intpre,intin,int s, int e){
static int i = 0;
if(s>e){
return NULL;
}
int idx = -1;
noderoot = new node(pre[i]);
for( int j = s; j<= e; j++){
if(pre[i] == in[j]){
idx = j;
break;
}
}
i++;
root->left = builttree(pre,in,s,idx-1);
root->right = builttree(pre,in,idx+1,e);
return root;
}
nodetargetnode(noderoot,int A){
if(root==NULL){
return NULL;
}
nodetemp;
if(root->data == A){
return root;
}
node ls = targetnode(root->left,A);
if( ls == NULL){
return targetnode(root->right,A);
}
return ls;
}
void printkthlevel(noderoot, int k){
if(root == NULL){
return;
}
if( k==1 ){
cout << root->data << " ";
}
printkthlevel(root->left,k-1);
printkthlevel(root->right,k-1);
return;
}
int printatdistancK(noderoot,nodetarget,int k){
if(root == NULL){
return -1;
}
//reac the target node
if(root == target){
printkthlevel(target,k+1);
return 0;
}
// next step - ancestor
int DL = printatdistancK(root->left,target,k);
if(DL!= -1){
//two cases ancestor or
if(DL+1 == k){
cout << root->data << " ";
}
else{
printkthlevel(root->right,k-DL-1);
}
return 1+DL;
}
int DR = printatdistancK(root->right,target,k);
if(DR!= -1){
//two cases ancestor or
if(DR+1 == k){
cout << root->data << " ";
}
else{
printkthlevel(root->left,k-DR-1);
}
return 1+DR;
}
return -1;
}
int main() {
int n;
cin >>n;
int pre[n];
int in[n];
for( int i = 0; i<n; i++){
cin >> pre[i];
}
for( int i = 0; i<n; i++){
cin >>in[i];
}
int t;
cin >> t;
noderoot = builttree(pre,in,0,n-1);
while(t–){
int A,k;
cin >> A>>k;
node*target = targetnode(root,A);
int a = printatdistancK(root,target,k);
cout << a << endl;
cout << endl;
}
return 0;
}