Campeonato de sumo P19521

En este problema te pedimos que simules un campeonato de luchas de robots de sumo. Las reglas del campeonato son muy sencillas:

• Los robots se dividen en 4 grupos, de al menos 2 robots por grupo. Es posible que no todos los grupos tengan el mismo tamaño (en la versión fácil del problema, todos los grupos seran de 4 robots).

• Dentro de cada grupo, los robots hacen una liguilla: todos luchan contra todos, una sola partida. El ganador recibe 1 punto, el perdedor 0.

• Los robots se ordenan dentro de cada grupo, primero por puntos y, en caso de empate, por orden alfabético de sus nombres (por ejemplo, si Aaron y Chuck empataran a puntos, ganaría Aaron). (En la version facil del problema, no es necesario hacer nada mas).

• Los dos mejores de cada grupo pasan a los cuartos de final, donde se emparejan del siguiente modo:

En este concurso, además, hay una pequeña novedad. Los combates no se realizan según un orden establecido, sinó que se sigue la filosofía de tatami abierto (open tatami): cualquier par de robots pueden decidir enfrentarse en el tatami en cualquier momento (pertenezcan o no al mismo grupo, estén o no estén eliminados, etc.). Si su combate es uno de los combates previstos en el calendario, entonces deberá contabilizarse para el campeonato; de otro modo, el resultado de este combate deberá ignorarse. Por ignorar, entendemos que ese resultado no tiene ninguna validez, y que si más adelante los dos robots deben enfrentarse, es necesario que vuelvan a luchar. En concreto, deberán ignorarse los siguientes combates:

• Durante la fase de liguilla, se ignorará cualquier combate que enfrente a robots de grupos distintos, o a robots del mismo grupo que ya se hubieran enfrentado anteriormente. Se pasa a la fase final cuando, para cada grupo, todos los robots que lo forman se han enfrentado entre sí una vez.

• Durante la fase final, se ignorará cualquier combate entre robots no emparejados: por ejemplo, si alguno de ellos está eliminado, o si están emparejados con otros robots.

En particular, durante la fase final es posible que un robot llegue a la final, y a la vez, que otros robots todavía no hayan hecho su combate de cuartos de final.

Entrada

La entrada empieza con cuatro líneas, cada una de las cuales tiene un número $k\geq 2$, seguido de los $k$ nombres (secuencias de no más de 10 letras y dígitos, sin espacios) de los robots que forman parte de los grupos A, B, C y D, respectivamente. Todos los robots tienen nombres distintos.

A continuación, una secuencia de tripletas R1 R2 x, separadas por una cantidad arbitraria de espacios y saltos de línea, donde R1 y R2 son los nombres de 2 robots, y $x$ es $1$ o $2$ para indicar que el robot R1 ha ganado un combate contra el robot R2 ($x=1$) o que R2 ha ganado un combate contra el robot R1 ($x=2$).

Salida

Si no hay suficientes combates para decidir la fase de liguilla (es decir, si no ocurre que todos los robots de todos los grupos han luchado contra todos los de su mismo grupo), escribe una línea con el texto ??.

Si se puede acabar de disputar la liguilla, escribe 8 líneas con los nombres de los robots ganadores, emparejados como se muestra en el esquema anterior (la primera línea contendrá el ganador del grupo A; la siguiente, el segundo clasificado del grupo D; luego 1B, 2C, 1C, 2B, 1D, 2A.

Si, además, hay suficientes combates para disputar la fase final, escribe una línea con cinco guiones (-----) y otras cuatro líneas: la primera y la segunda con los nombres del robot ganador y finalista, la tercera línea con los dos nombres de los robots que perdieron las semifinales, y la cuarta con los cuatro nombres de los robots que perdieron los cuartos de final. En estos dos últimos casos, escribe los nombres separados por espacios y en orden alfabético (según los códigos ASCII de las letras).

Puntuación

• Test1:

  Resolver 20 entradas donde todos los grupos son de 4 robots, y donde nunca se llega a completar la fase final.

• Test2:

  Resolver 20 entradas de todo tipo, donde los grupos no tienen más de 10 robots cada uno.