En un universo paralelo, los patos ganaron a los primates en la línea evolutiva y ahora son la especie dominante.

En un dia de entretenimiento pueden ir a la ciudad a darles de comer pan seco a los humanos, ir al cine a ver peliculones como "Acero Puro" (“CUACero puro” en su versión adaptada), e ir a Escape Rooms ambientadas en descender por plataformas.

Las plataformas tienen agujeros y muros. Los patos vuelan pero no tanto, por lo tanto pueden caer o saltar por encima de los agujeros, pero los muros no se pueden sortear.

¡Ayuda al pato a pisar la plataforma final superando los niveles!

ENTRADA

Cada caso consta de una línea con dos números: F y C, seguida de una matriz de F*C que describe la descripción de las plataformas:

C → Es suelo sobre el que puede pisar y desplazarse.

A → Es un agujero, por el que se puede descender a la siguiente plataforma (o desplazar horizontalmente por la misma).

M → Es un muro, cuyo impedimento hace que solo puedas volver por donde has venido.

Aclaraciones:

• El pato empieza el juego desde la plataforma de Nivel 1 desde el lado izquierdo, donde se asegura que no se topará un muro de primeras. (La primera plataforma puede contener muros).

• La plataforma final será toda únicamente “C”.

• Si caes encima de un muro, NO se puede acceder a esa plataforma en la que se encuentra el muro.

SALIDA

Si llega a pisar la plataforma final --> imprime "WIN"

Si no llega --> retorna el nivel de la plataforma máximo al que puede aspirar a llegar.

EJEMPLO DE ENTRADA 1

5 4
C A M A
M C A M
A M C A
C A M C
C C C C

EJEMPLO DE SALIDA 1

4

EJEMPLO DE ENTRADA 2

5 5
C A M C C
A C M C A
C A M C C
C C A C M
C C C C C

EJEMPLO DE SALIDA 2

WIN