Autores: Martín Andrighetti, Gabriel Carmona, Benjamín Letelier

Tiempo límite: 2 segundos

Memoria límite: 256 megabytes

Chuntaro Furukagua, presidente de Noentiendo Co., observa con preocupación cómo su compañía atraviesa una crisis. Apenas les quedan \(1000\) pesos para desarrollar un último juego que podría salvarlos de la quiebra.

En medio de la desesperación, Chijeru Millamoto, creador del famoso fontanero italiano Nachino, propone una idea que puede realizarse exactamente con ese presupuesto.

El juego consiste en un mundo representado por una línea, la cual puede contener obstáculos imposibles de atravesar. El protagonista comienza en la posición \(a\) y su objetivo es encontrar el tesoro mágico. Si los obstáculos hacen que el tesoro sea inalcanzable, el jugador pierde. En caso contrario, gana.

Dado que ninguno de sus empleados está dispuesto a trabajar por apenas \(1000\) pesos, Millamoto pide tu ayuda para programar este juego y así intentar salvar la compañía.

Entrada

La primera línea contiene un entero \(n\) (\(2 \le n\le 1000\)), que indica la cantidad de posiciones en el mundo.

La segunda línea contiene un string \(s\) de largo \(n\), donde cada carácter representa una posición:

• .: posición libre, sin obstáculo
• #: posición con obstáculo
• A: posición inicial del protagonista
• T: posición del tesoro

Se asegura que solo hay una posición donde aparece el carácter A y otra donde aparece el carácter T.

Salida

Imprime “ganaste” si el tesoro es alcanzable por el jugador, en caso contrario imprime “perdiste”.

Ejemplos

Entrada 1

6
..A..T

Salida 1

ganaste

Entrada 2

6
..A#.T

Salida 2

perdiste