En un árbol binario de búsqueda (ABB), para cada nodo, todos los valores de su subárbol izquierdo son menores que el suyo y todos los de su subárbol derecho son mayores.

El ancestro común más bajo de dos nodos \(p\) y \(q\) es el nodo más profundo que tiene a ambos en su subárbol (un nodo está en su propio subárbol, así que puede ser \(p\) o \(q\)). Dado un ABB y varias consultas, responde el ancestro común más bajo de cada par.

Entrada

El árbol viene en el formato de LeetCode, en dos líneas: la primera tiene un entero \(k\) y la segunda \(k\) elementos separados por espacios, que son el recorrido por niveles del árbol. Cada elemento es el valor de un nodo o null si ese hijo no existe; los hijos de un null no se escriben y los null del final se omiten. Un árbol vacío se escribe con \(k = 0\) y una línea vacía.

Después viene una línea con \(k\) \((1 \le k \le 100)\) y \(k\) líneas con dos valores \(p\) y \(q\) que están en el árbol (pueden ser iguales). El árbol tiene entre \(2\) y \(2 \cdot 10^4\) nodos con valores distintos \((|v| \le 10^9)\), y altura a lo más \(1000\).

Salida

Para cada consulta, una línea con el valor del ancestro común más bajo.

Ejemplo 1

Entrada

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

Salida

2
6
2

Ejemplo 2

Entrada

2
2 1
1
2 1

Salida

2

Basado en el problema 235 de LeetCode, Lowest Common Ancestor of a Binary Search Tree, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.