Implementa un trie, un árbol donde cada arista es una letra y cada palabra es un camino desde la raíz. Debe soportar:

• insert w: agrega la palabra \(w\).
• search w: imprime true si la palabra \(w\) fue agregada antes (completa) o false si no.
• prefix p: imprime true si alguna palabra agregada antes empieza con \(p\) o false si no.

Entrada

La primera línea tiene \(q\) \((1 \le q \le 5 \cdot 10^4)\) y siguen \(q\) líneas con una operación cada una. Las palabras son de letras minúsculas, de largo entre \(1\) y \(30\).

Salida

Una línea por cada search y prefix, con su respuesta.

Ejemplo 1

Entrada

6
insert apple
search apple
search app
prefix app
insert app
search app

Salida

true
false
true
true

Ejemplo 2

Entrada

4
search a
prefix a
insert ab
prefix a

Salida

false
false
true

Basado en el problema 208 de LeetCode, Implement Trie (Prefix Tree), adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.