Ahoy!


image imagem
Ahoy marujos! Vamos juntos embarcar numa grande aventura, por mares nunca dantes navegados! Na distante ilha de Sapot, lá no Mar das Caraíbas, está enterrado um valioso tesouro, perdido desde a trágica expedição do saudoso Barba Negra. Está na hora de o recuperar!

O Barba Negra, minutos antes de naufragar, conseguiu desenhar num mapa da ilha o caminho para o tesouro. Mapa esse que já chegou à nossa posse, Aye! Mas a tormenta era tanta que o Barba Negra teve pouco tempo para verificar o rascunho e com grande probabilidade o mapa pode não levar ao tesouro, mas sim às perigosas armadilhas de Sapot. Aaaarrrrgggghhhh!

A vossa participação nesta viagem é importantíssima! Se vos mostrarmos o mapa, ainda antes da partida, conseguem-nos dizer se o caminho traçado nos leva ao tesouro ou diretos a uma das armadilhas? Se for o último caso, nem zarpamos!

A ilha de Sapot é um perfeito retângulo. Por exemplo, se o mapa deixado pelo Barba Negra for o seguinte:

E  S  A
S  S  N
A  X  N
A  A  A

e se assumirmos que atracamos na ilha no canto superior esquerdo, chegamos ao tesouro. A explicação é a seguinte:
  1. Ao chegarmos à ilha, o mapa manda-nos em direção a este, já que lemos a letra E.

  2. De seguida, continuamos para sul (letra S).

  3. Depois, vamos novamente para sul (letra S).

  4. E, finalmente, chegamos ao tesouro! Como sempre, a letra X marca o local!
As letras N, S, E e O indicam, respetivamente, que devemos continuar para norte, sul, este e oeste. O local do tesouro está assinalado com a letra X e as várias armadilhas estão assinaladas com a letra A.

Tarefa

Escreva um programa que, dada a dimensão da ilha de Sapot e o mapa do tesouro, indica se a expedição conseguirá chegar ao tesouro ou se irá cair numa das armadilhas. A caça ao tesouro começa sempre pelo ponto mais a norte e a oeste da ilha, isto é, pelo canto superior esquerdo do mapa.

Assuma que nunca é possível que o mapa o leve para fora dos limites da ilha. Por exemplo, não será possível encontrar-se na borda mais a este da ilha e ler no mapa a letra E, o que o obrigaria a saltar para o mar.

Deve também assumir que o mapa nunca o levará por caminhos cíclicos. Por exemplo, não será possível ler no mapa a letra E e logo de seguida a letra O, ficando para sempre encurralado.

Input

A primeira linha do input contém dois inteiros, L e C, que representam, respetivamente, o número de linhas e o número de colunas da ilha (e do mapa). De seguida, há L linhas, cada uma com C letras, que só podem ser N, S, E, O, X ou A. As letras estão separadas por um único espaço.

Restrições

  1≤L≤50 Número de linhas do mapa
  1≤C≤50 Número de colunas do mapa

Output

O output tem uma única linha, com a palavra: "Tesouro", se o tesouro for encontrado; "Armadilha", nos restantes casos.

Exemplo 1

Input 

4 3
E S A
S S N
A X N
A A A

Output 

Tesouro

Exemplo 2

Input 

4 4
E E E S
E A S O
E X A N
N N O O

Output 

Armadilha

Exemplo 3

Input 

4 4
A E E S
E A S O
E X A N
N N O O

Output 

Armadilha

Exemplo 4

Input 

4 4
X E E S
E A S O
E A A N
N N O O

Output 

Tesouro


ToPAS'2025