SPOJ Brasil

O famoso bruxo está de volta. Depois de matar um incrível número de monstros para achar um tesouro escondido, Zak Galou decidiu comprar vinhedos na Borgonha e se aposentou. Tudo estava calmo em sua nova vida, até que um dia seu trator parou de funcionar.

O motor de seu trator funciona baseado em um mecanismo de rodas dentadas. O motor pode ser representado por uma grade bidimensional. No máximo uma roda dentada pode ser presa a cada posição da grade. Todas as engrenagens são idênticas e podem engrenar com as rodas adjacentes. Nessa grade, uma roda dentada pode ter até seis engrenagens adjacentes, veja a figura abaixo:

Em condições normais, quando o trator é ligado, algumas das engrenagens são inicialmente ativadas e tentam giram em sentido horário. Quando uma engrenagem tenta girar em um sentido, todas as outras adjacentes tentam girar no sentido oposto.

Quando Zak Galou abriu o motor ele percebeu que ele havia sido sabotado (provavelmente por um caçador de tesouros que não conseguiu achar o tesouro). Algumas das engrenagens foram removidas do motor e outras adicionadas. Como conseqüência, algumas engrenagens estavam imóveis. Uma engrenagem pode estar imóvel tanto quando ela está livre ou está bloqueada. Uma engrenagem está livre quando ela não é ativada inicialmente e não tem nenhuma engrenagem adjacente tentando girar. Uma engrenagem está bloqueada quando ela está tentando girar em ambos sentidos ao mesmo tempo. Por exemplo, considere que existam três engrenagens no motor como mostrado na figura abaixo. Se qualquer uma delas é ativada inicialmente, todas estarão bloqueadas. Se nenhuma delas é ativada inicialmente, todas estarão livres.

Como parte do trabalho para consertar seu trator, Zak Galou pede sua ajuda para resolver o seguinte problema. Dada a descrição do motor e das engrenagens que estão ativadas inicialmente em sentido horário, ele quer saber para cada uma delas qual o seu estado quando o trator é ligado: girando no sentido horário, girando no sentido horário, livre ou bloqueado.

Entrada

A entrada contém diversos casos de teste. A primeira linha de um caso de teste contém dois inteiros R e C, separados por um espaço, representando respectivamente o número de fileiras e colunas da grade do motor (1 <= R, C <= 100). As próximas R linhas descrevem o motor. A i-ésima linha representa a i-ésima fileira do motor e contém C caracteres. O caractere “.” indica que não existem engrenagens naquela posição, o caractere “*” indica que existe uma engrenagem que não é ativada inicialmente e um “I” indica que existe uma engrenagem que é inicialmente ativada quando o motor é ligado. Perceba que, por razões de simplicidade, o paralelogramo representando a grade do motor é descrito na entrada como se fosse um retângulo com cada fileira alinhada à esquerda. O final da entrada é indicado por R = C = 0.

Saída

Para cada caso de teste, seu programa deve imprimir R + 1 linhas. A primeira linha deve estar vazia; cada uma das R linhas seguintes deve ter C caracteres. Os caracteres impressos devem representar o estado de cada posição da grade quando o motor é ligado. Imprima um “.” se não existem engrenagens na posição; um “(“ se existe uma engrenagem girando em sentido horário; um “)” se existe uma engrenagem girando em sentido anti-horário; um “F” maiúsculo se existe uma engrenagem que está livre e um “B” maiúsculo se existe uma engrenagem bloqueada.

Exemplo

Entrada
4 3
...
.*.
.I.
...
4 4
....
.**.
.I..
..*.
0 0

Saída
...
.).
.(.
...
....
.BB.
.B..
..F.