El joc de l'OSO P41805

L’Anna i en Bernat estan jugant al joc de l’OSO, en una versió simplificada. Suposeu un tauler $n \times m$, inicialment buit, on per torns s’hi ha de posar una ‘S’ o una ‘O’ a qualsevol casella lliure. Sempre comença a jugar l’Anna. Guanya el primer que aconsegueix escriure “OSO” horitzontalment o verticalment (no diagonalment). Si el tauler s’omple sense que ningú aconsegueixi fer un “OSO”, la partida acaba en empat.

Donades les $n \cdot m$ jugades que s’intentaran fer en un tauler inicialment buit, escriviu el nom del guanyador o bé si hi ha hagut empat. A més, escriviu el contingut del tauler quan s’ha acabat la partida, ja sigui perquè algú ha guanyat o perque s’han omplert totes les posicions.

Entrada

L’entrada té diverses partides. Cada partida comença amb les mides del tauler $n$ i $m$, seguides de $n \cdot m$ jugades, cadascuna amb una fila entre 0 i $n-1$, una columna entre 0 i $m-1$, i un caràcter que és ‘S’ o ‘O’. Suposeu $1 \le n \cdot m \le 10^5$, i que totes les posicions donades són diferents.

Sortida

Per a cada partida, escriviu “Anna”, “Bernat”, o bé “empat”. A continuació, escriviu l’estat final de la partida. Marqueu amb punts les posicions on no s’ha arribat a jugar. Escriviu una línia buida al final de cada cas.