Least Common Ancestor in a Binary Search Tree

You are given a fixed binary search tree (BST) defined as follows:

         6
       /   \
      2     8
     / \   / \
    0   4 7   9
       / \
      3   5

Your task is to find the least common ancestor (LCA) of two nodes in this BST. The LCA of two nodes p and q is defined as the deepest node that has both p and q as descendants (where we allow a node to be a descendant of itself).

You will be given two integers p and q as input. You must locate the nodes in the BST with these values and output the value of their LCA.

Note: The BST is fixed and is constructed as shown above.

inputFormat

The input consists of a single line containing two space-separated integers. These integers represent the values of nodes p and q in the BST. It is guaranteed that both values exist in the tree.

outputFormat

Output a single integer that is the value of the least common ancestor of nodes p and q.## sample

2 8

6