Let T be a rooted tree. The Lowest Common Ancestor(LCA) between two nodes n1 and n2 is the lowest node in T with both n1 and n2 as descendants (we allow a node to be its descendant).

The LCA of n1 and n2 in T is the shared ancestor of n1 and n2 located farthest from the root. Computation of lowest common ancestors may be helpful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree.

Let's assume two nodes of a BST are n1 and n2. Your task is to find out their LCA. For example, suppose the status of the tree is as follows:

20

/ \

8 22

/ \

4 12

/ \

10 14

LCA of 10 & 14: 12

LCA of 4 & 22: 20

LCA of 4 & 8 : 8

LCA of 4 & 12 :8 (20 is also a common ancestor, but not 'lowest')

LCA of 8 & 14: 8

LCA of 8 & 22: 20

LCA of 20 & 8 : 20

LCA of 10 & 12: 12

Steps:

• At first, a sequence of N integers will be inserted (until -1)
• The numbers are inserted in an AVL Tree. The final status of the tree shown after all nodes are inserted.
• Then there will be a number T, followed by T pairs of n1 & n2
• For each pair, your task is to print the LCA.

(PTO)

Sample Input

Input sequence

12 9 5 11 20 15 7 3 6 27 -1

11

3 6

6 11

27 9

12 27

27 12

6 7

9 3

7 20

20 15

11 7

11 27

Sample Output

Status: 3(0) 5(0) 6(0) 7(0) 9(-1) 11(0) 12(1) 15(0) 20(0) 27(0)

5

7

12

12

12

7

7

12

20

7

12

Note:

• Use AVL Tree
• The solution must be O(logN)

12(1)

/ \

7(0) 20(0)

/ \ / \

5(0) 9(0) 15(0) 27(0)

/ \ \

3(0) 6(0) 11(0)