import java.util.*;
public class Main {
static class BinaryTree {
static int preIndex = 0;
private class Node {
int data;
Node left;// left child
Node right;// right child
int depth;
Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
Node(int data) {
this.data = data;
this.left = this.right = null;
}
}
Node root = null;
int size = 0;
// BinaryTree() {
//
// Scanner sc = new Scanner(System.in);
// this.root = takeInput(sc, null, false);// parent = null,true or false if its right or left child
// }
BinaryTree(int[] io, int[] pre, int si, int ei) {
this.root = build(io, pre, si, ei);
}
private Node takeInput(Scanner sc, Node parent, boolean isLeftOrRight) {
if (parent == null) {
System.out.println("Enter the data for root node");
} else {
if (isLeftOrRight) {// if true then it is for left child
System.out.println("Enter the data for left child of " + parent.data);
} else {// false therefore right child
System.out.println("Enter the data for right child of " + parent.data);
}
}
int nodeData = sc.nextInt();// take node data
Node node = new Node(nodeData, null, null);// create a new node
this.size++;// inc size of tree
boolean choice = false;// choice variable to keep track if user wants to enter left or right child
System.out.println("Do you have left child of " + node.data);
choice = sc.nextBoolean();
if (choice) {
node.left = takeInput(sc, node, true);// take input recursively for the child,parent = node,true as it
// was
// the left child
}
choice = false;
System.out.println("Do you have right child of " + node.data);
choice = sc.nextBoolean();
if (choice) {
node.right = takeInput(sc, node, false);// take input recursively for the child,parent = node,false as
// it
// was the right child
}
return node;// return node to the constructor
}
public void depth() {
depth(this.root, 0);
}
private void depth(Node node, int d) {
if (node != null) {
node.depth = d;
depth(node.left, d + 1);
depth(node.right, d + 1);
}
}
public void display() {// public function for the class object to access
this.display(this.root);
}
private void display(Node node) {
String str = "";
if (node.left != null) {
str += node.left.data + "=>";// if node has left child then add it
} else {
str += "END=>";
}
str += node.data;
if (node.right != null) {// if node has right child add it
str += "<=" + node.right.data;
} else {
str += "<=END";
}
System.out.println(str);// print the string
if (node.left != null) {
display(node.left);// recursively call function for left child
}
if (node.right != null) {
display(node.right);// recursively call function for right child
}
}
public int height() {
return this.height(this.root);
}
public int height(Node node) {
if (node == null) {
return -1;
}
int lheight = this.height(node.left);
int rhreight = this.height(node.right);
int height = Math.max(lheight, rhreight) + 1;
return height;
}
public void postOrder() {
this.postOrder(this.root);
}
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data + " ");
}
public void preOrder() {
this.preOrder(this.root);
}
private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
public void inOrder() {
this.inOrder(this.root);
}
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
public void levelOrder() {
LinkedList<Node> queue = new LinkedList<>();
queue.add(this.root);
while (!queue.isEmpty()) {
Node rv = queue.removeFirst();
System.out.print(rv.data + ", ");
if (rv.left != null) {
queue.addLast(rv.left);
}
if (rv.right != null) {
queue.addLast(rv.right);
}
}
System.out.println("END");
}
public boolean isBST() {
return this.isBST(this.root, Integer.MIN_VALUE, Integer.MAX_VALUE);// root node's min and max value are
// -infinity to infinity
}
private boolean isBST(Node node, int min, int max) {
if (node == null) {// if we reached to null node therefore before this all satisfied bst property
// therefore return true
return true;
}
if (node.data > max || node.data < min) {// if node.data is not in range return false
return false;
} else if (!this.isBST(node.left, min, node.data)) {// if left node not in range return false,range =
// min,node.data,recursive call
return false;
} else if (!this.isBST(node.right, node.data, max)) {// same recursive call to right subtree
return false;
}
return true;// return true if all calls came true
}
public List<Integer> inOrderIterative() {
return this.inOrderIterative(this.root);
}
private List<Integer> inOrderIterative(Node node) {
if (node == null) {
ArrayList<Integer> list = new ArrayList<>();
return list;
}
Stack<Node> stack = new Stack<>();
ArrayList<Integer> list = new ArrayList<>();
while (true) {
if (node != null) {
stack.push(node);
node = node.left;
} else {
if (stack.isEmpty()) {
break;
}
node = stack.pop();
list.add(node.data);
node = node.right;
}
}
return list;
}
public int diameter() {
return this.diameter(this.root);
}
private int diameter(Node node) {
if (node == null) {
return 0;
}
int case1 = this.height(node.left) + this.height(node.right) + 2;// diameter passes through root
int case2 = this.diameter(node.left);
int case3 = this.diameter(node.right);
int max = Math.max(case1, Math.max(case2, case3));
return max;
}
public int diameterBetter() {
return this.diameterBetter(this.root).diameter;// return the diameter of the tree
}
private DiaPair diameterBetter(Node node) {
if (node == null) {
DiaPair bp = new DiaPair(-1, 0);// if null encountered then height = -1 and diameter = 0
return bp;
}
DiaPair lp = this.diameterBetter(node.left);// recursive call to left node
DiaPair rp = this.diameterBetter(node.right);// recursive call to right node
DiaPair mp = new DiaPair();// mypair
mp.height = Math.max(lp.height, rp.height) + 1;// height = max of both ltree and rtree +1
mp.diameter = Math.max(lp.height + rp.height + 2, Math.max(lp.diameter, rp.diameter));// diameter as we did
// max
// of case1,2,3
return mp;// return our DiaPair
}
public class DiaPair {// class to save height and diameter at a node
int height;
int diameter;
DiaPair() {
}
DiaPair(int height, int diameter) {// parameterized constructor
this.height = height;
this.diameter = diameter;
}
}
public int sumLeaf() {
return this.sumLeaf(this.root);
}
private int sumLeaf(Node node) {
if (node == null) {// if node is null i.e. it is empty therefore return 0
return 0;
}
if (node.left == null && node.right == null) {// if node has no child i.e. it is leaf node therefore return
// its value
return node.data;
}
int lsum = sumLeaf(node.left);// recursive call to get left sum
int rsum = sumLeaf(node.right);// recursive call to get right sum
return lsum + rsum;// return total sum i.e. rsum + lsum
}
private Node build(int[] io, int[] pre, int si, int ei) {// to build tree from given inorder and preorder
// traversals
if (si > ei) {// if si gets greater then ei then return null as no node possible
return null;
}
Node temp = new Node(pre[preIndex++]);// create new node taking from pre order traversal, for preindex = 0
// its the root node in preorder traversal
if (si == ei) {// if si==ei i.e. its the only child node return it
return temp;
}
int idx = search(io, si, ei, temp.data);// search for the tempnode data in inorder traversal its index
temp.left = build(io, pre, si, idx - 1);// build tree for its left side from si to idx-1
temp.right = build(io, pre, idx + 1, ei);// build tree for its right side from idx+1 to ei
// as in inorder traversal left side is the left subtree of node and right sidde
// is the right subtree of the node
return temp;
}
private int search(int arr[], int si, int ei, int value) {// search for the value in inorder traversal array
int i;
for (i = si; i <= ei; i++) {
if (arr[i] == value)
return i;
}
return i;
}
// public void print(int e,int k) {
// this.print(getNode(this.root,e),k);
// this.print(this.root,e,k);
// }
// private int print(Node node,int e,int k) {
// if(node==null) {
// return -1;
// }
// if(node.data==e) {
// printd(node,k);
// return 0;
// }
// int dl = print(node.left,e,k);
// }
// private void printd(Node node,int k) {
// if(node==null||k<0) {
// return;
// }
// if(k==0) {
// System.out.print(node.data+" ");
// return;
// }
// print(node.left,k-1);
// print(node.right,k-1);
// }
private int k;
public void kdistance(int e, int d) {
k = d;
kdistance(getNode(this.root, e), d);
// System.out.println(inlc(getNode(root, e),this.root));
if (getNode(this.root, e) != this.root) {
kdistanceup(this.root, d - (getNode(this.root, e).depth - this.root.depth),
inlc(getNode(this.root, e), this.root));
}
}
private boolean inlc(Node n, Node p) {
if (p == null) {
return false;
}
if (p.left == n) {
return true;
} else if (p.right == n) {
return false;
} else {
if (p.left == null && p.right == null) {
return false;
}
if (p.left != null) {
return inlc(n, p.left);
}
return false;
}
}
private void kdistanceup(Node n, int d, boolean ilc) {
if (d > 0) {
if (n.left != null && !ilc) {
kdistance(n.left, d - 1);
} else if (n.right != null && ilc) {
kdistance(n.right, d - 1);
}
}
if (d < 0) {
if (ilc) {
kdistanceup(n.left, d + 1, inlc(n.left, n));
} else {
kdistanceup(n.right, d + 1, inlc(n.right, n));
}
return;
}
if (d == 0) {
System.out.print(n.data + " ");
}
}
private void kdistance(Node n, int d) {
if (k == 0) {
System.out.print("-1");
}
if (d == 0) {
System.out.print(n.data + " ");
}
if (n.left != null) {
kdistance(n.left, d - 1);
}
if (n.right != null) {
kdistance(n.right, d - 1);
}
}
private Node getNode(Node node, int e) {
if (node == null || node.data == e) {
return node;
}
Node rr = getNode(node.left, e);
if (rr == null) {
rr = getNode(node.right, e);
}
return rr;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] io = new int[n];
int[] pre = new int[n];
for (int i = 0; i < n; i++) {
pre[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
io[i] = sc.nextInt();
}
BinaryTree tree = new BinaryTree(io, pre, 0, n - 1);
int t = sc.nextInt();
while (t-- != 0) {
int e = sc.nextInt();
int d = sc.nextInt();
// tree.print(e,d);
tree.depth();
tree.kdistance(e, d);
System.out.println();
}
// tree.display();
}
}