En una carrera de \(N\) caballos (sin empates; todos llegan) se conoce el resultado de \(R\) carreras chicas: cada una es un subconjunto de los caballos junto con el puesto en la carrera completa de su ganador (el ganador de una carrera chica es el mejor ubicado de sus participantes en la carrera completa).

Encuentra un orden de llegada de la carrera completa que sea consistente con todas las carreras chicas.

Entrada

La primera línea tiene un entero \(N\) \((2 \le N \le 300)\). La segunda línea tiene \(N\) nombres distintos, cada uno de hasta tres letras minúsculas.

La tercera línea tiene un entero \(R\) \((1 \le R \le 10^5)\). Cada una de las siguientes \(R\) líneas describe una carrera chica con dos enteros \(M_i\) \((2 \le M_i \le N)\) y \(W_i\) \((1 \le W_i \le N)\), seguidos de los \(M_i\) nombres distintos de sus participantes: su ganador quedó en el puesto \(W_i\) de la carrera completa. Se garantiza que \(\sum M_i \le 10^5\) y que existe al menos una solución.

Salida

Una línea con los \(N\) nombres en un orden de llegada válido. Si hay varios, cualquiera es aceptado.

Ejemplo 1

Entrada

5
a b c d e
3
4 2 a b c d
2 4 b d
2 2 c b

Salida

e c a b d

Ejemplo 2

Entrada

2
aaa b
3
2 1 aaa b
2 1 b aaa
2 1 aaa b

Salida

b aaa

Regional Latinoamericana 2022 del ICPC, problema H («Horse Race»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.