Lowest Common Ancestor in a Binary Tree

Given a binary tree and two integer values p and q, find the lowest common ancestor (LCA) of the two nodes with these values. The lowest common ancestor of two nodes p and q in a tree is defined as the deepest node \(a\) such that both \(p\) and \(q\) are in its subtree (a node can be a descendant of itself).

The binary tree will be given in level order (breadth-first) traversal, where the keyword null represents a missing node. It is guaranteed that both p and q exist in the tree and that all node values are unique.

Your task is to output the value of the node that represents the lowest common ancestor of p and q.

inputFormat

The input consists of two lines:

1. The first line contains the level order traversal of the binary tree. Each value is separated by a space. Use the string null (without quotes) to represent a missing node.
2. The second line contains two integers p and q separated by a space, representing the values of the two nodes for which you need to find the LCA.

Example:

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

outputFormat

Output a single integer which is the value of the lowest common ancestor of the nodes with values p and q.

Example:

3

## sample

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

3