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
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(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 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;
}
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 void kdistance(int e, int d) {
// List ans = kdistance(this.root, getNode(this.root, e), d);
// for(int x:ans) {
// System.out.print(x+" ");
// }
// }
//
// private List kdistance(Node node, Node target, int K) {
// List dist = new ArrayList();
//
// if (K == 0) {
// dist.add(target.data);
// return dist;
// }
// traverse(dist, node, target, K, 0);
// return dist;
// }
//
// private int traverse(List dist, Node node, Node target, int k, int val) {
// if (node == null)
// return 0;
//
// if (val == k) {
// dist.add(node.data);
// return 0;
// }
// int left = 0, right = 0;
//
// if (node.data == target.data || val > 0) {
// left = traverse(dist, node.left, target, k, val + 1);
// right = traverse(dist, node.right, target, k, val + 1);
// } else {
// left = traverse(dist, node.left, target, k, val);
// right = traverse(dist, node.right, target, k, val);
// }
// if (left == k || right == k) {
// dist.add(node.data);
// return 0;
// }
// if (node.data == target.data) {
// return 1;
// }
// if (left > 0) {
// traverse(dist, node.right, target, k, left + 1);
// }
// if (right > 0) {
// traverse(dist, node.left, target, k, right + 1);
// }
// if (left > 0 || right > 0) {
// return left > 0 ? left + 1 : right + 1;
// }
//
// return 0;
// }
//
//
void printkdistanceNodeDown(Node node, int k)
{
// Base Case
if (node == null || k < 0)
return;
// If we reach a k distant node, print it
if (k == 0)
{
System.out.print(node.data + " ");
return;
}
// Recur for left and right subtrees
printkdistanceNodeDown(node.left, k - 1);
printkdistanceNodeDown(node.right, k - 1);
}
// Prints all nodes at distance k from a given target node.
// The k distant nodes may be upward or downward.This function
// Returns distance of root from target node, it returns -1
// if target node is not present in tree rooted with root.
int printkdistanceNode(Node node, Node target, int k)
{
// Base Case 1: If tree is empty, return -1
if (node == null)
return -1;
// If target is same as root. Use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if (node == target)
{
printkdistanceNodeDown(node, k);
return 0;
}
// Recur for left subtree
int dl = printkdistanceNode(node.left, target, k);
// Check if target node was found in left subtree
if (dl != -1)
{
// If root is at distance k from target, print root
// Note that dl is Distance of root's left child from
// target
if (dl + 1 == k)
{
System.out.print(node.data + " ");
}
// Else go to right subtree and print all k-dl-2 distant nodes
// Note that the right child is 2 edges away from left child
else
printkdistanceNodeDown(node.right, k - dl - 2);
// Add 1 to the distance and return value for parent calls
return 1 + dl;
}
// MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
// Note that we reach here only when node was not found in left
// subtree
int dr = printkdistanceNode(node.right, target, k);
if (dr != -1)
{
if (dr + 1 == k)
{
System.out.print(node.data+" ");
}
else
printkdistanceNodeDown(node.left, k - dr - 2);
return 1 + dr;
}
// If target was neither present in left nor in right subtree
return -1;
}
public void printkdistanceNode(int e, int d) {
printkdistanceNode(this.root,getNode(root, e), d);
}
}
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.kdistance(e, d);
tree.printkdistanceNode(e, d);
System.out.println();
}
}
}
