En LeetCode se pide diseñar cómo convertir un árbol binario en texto (serializar) y cómo reconstruirlo desde ese texto (deserializar). Aquí los dos formatos están fijos y hay que convertir entre ellos:

• Por niveles (el formato de LeetCode): el recorrido por niveles, con null para los hijos que faltan; los hijos de un null no se escriben y los null del final se omiten. El árbol vacío no tiene elementos.
• Preorden con marcas: la raíz, luego el subárbol izquierdo y luego el derecho, cada uno en este mismo formato; un árbol vacío se escribe #. Por ejemplo, un nodo 1 con un solo hijo izquierdo 2 es 1 2 # # #.

Cada consulta es S: llega un árbol por niveles y hay que imprimirlo en preorden con marcas; o D: al revés.

Entrada

La primera línea tiene \(T\) \((1 \le T \le 30)\). Cada consulta viene en dos líneas: la letra S o D seguida de la cantidad \(k\) de elementos, y luego los \(k\) elementos. Cada árbol tiene a lo más \(10^4\) nodos, altura a lo más \(1000\) y valores \(|v| \le 1000\); en total hay a lo más \(5 \cdot 10^4\) nodos.

Salida

Para cada consulta, una línea con la cantidad de elementos de la respuesta seguida de los elementos.

Ejemplo 1

Entrada

2
S 7
1 2 3 null null 4 5
D 11
1 2 # # 3 4 # # 5 # #

Salida

11 1 2 # # 3 4 # # 5 # #
7 1 2 3 null null 4 5

Ejemplo 2

Entrada

2
S 0

D 1
#

Salida

1 #
0

Basado en el problema 297 de LeetCode, Serialize and Deserialize Binary Tree, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.