Mariano y Luisito P37276

– Mariano, que este nivel es muy chungo! –dice Luisito.

– Venga hombre, que no es para tanto! –responde Mariano. Sólo hay que superar este pasillo de ancho A y largo L. Aquí tengo un mapa completo, ves? Nosotros empezamos arriba de todo, donde la ‘M’. Los puntos son casillas vacías, y los asteriscos son obstáculos. El scroll hace que, automáticamente y sin tocar ninguna tecla, cada turno bajemos una casilla. Además, si apretamos las teclas “izquierda” o “derecha”, bajaremos en diagonal, y así podremos evitar los obstáculos hasta llegar abajo del todo.

– Y estas marcas? Son tesoros?

– Déjame ver …pues no, la ‘T’ es de Trampa.

– Me lo temía! Venga Mariano, vámonos a casa.

– Espera, las trampas no son mortales. Si cayéramos en una, podríamos escapar apretando tres veces la tecla “arriba”. Venga Luisito, que descubrir el camino óptimo está chupado.

Haced un programa que calcule el mínimo número de pulsaciones necesarias para superar el nivel.

Entrada

La entrada empieza con los números 3 ≤ A ≤ 80 y 3 ≤ L ≤ 10000, seguidos de L líneas con A caracteres que representan el mapa. La primera línea contiene exactamente una ‘M’. Los restantes caracteres representan casillas vacías ‘.’, obstáculos ‘*’ o trampas ‘T’.

Salida

Escribid el mínimo número de pulsaciones necesarias para superar el nivel. Si no es posible, escribid “IMPOSIBLE”.