Lowest Common Ancestor in a Binary Tree

Given a binary tree, your task is to find the lowest common ancestor (LCA) of two given nodes. The LCA of two nodes \(p\) and \(q\) in a binary tree 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).

The binary tree is provided in a level-order serialization where missing nodes are represented by the string "null". The values in the tree are guaranteed to be unique. You are also given two target values representing \(p\) and \(q\). Your task is to determine and output the value of their lowest common ancestor.

Example:

Input:
3 5 1 6 2 0 8 null null 7 4
5 1
Output:
3

</p>

In the above example, the tree is constructed as follows:

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

and the LCA of the nodes with values 5 and 1 is 3.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains a space-separated list of tokens representing the binary tree in level-order. Use the string null to denote a missing node.
2. The second line contains two integers p and q separated by a space. These are the values of the two nodes for which you must determine the lowest common ancestor.

It is guaranteed that both p and q exist in the tree and that all node values are unique.

outputFormat

Output to stdout a single integer representing the value of the lowest common ancestor of the nodes with values p and q.

## sample

3 5 1 6 2 0 8 null null 7 4
5 1

3