Given a binary tree (not necessarily a BST), find the lowest common ancestor (LCA) of two given nodes p and q.

The LCA is the lowest node that has both p and q as descendants (a node is a descendant of itself).

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes is in the range [2, 10⁵]
• -10⁹ ≤ Node.val ≤ 10⁹
• All Node.val are unique
• p != q, both p and q exist in the tree

Input format: First line: BFS level-order. Second line: value of p. Third line: value of q.

Output format: The value of the LCA node.