Samus Aran és la dona protagonista de la famosa saga de videojocs Metroid, i una de les moltes habilitats que té al seu abast és disparar el seu canó d'energia en diferents direccions.

Donada una matriu d'elements i una direcció del dispar de la Samus, cal dir si el dispar toca algun enemic, tenint en compte que el dispar sempre avança fins fer contacte amb algun element o fins que surt de la pantalla.

La Samus sempre es trobarà a la cantonada inferior esquerra de la matriu (que representa la pantalla) i es representa amb el caràcter @, i pot disparar cap amunt (el projectil avança en línia recta cap amunt) i cap a la dreta (el projectil avança en línia recta cap la dreta).

Els altres elements que poden aparèixer a la matriu són els obstacles, que es representen amb el caràcter #, i els enemics, que es representen amb el caràcter &; finalment, els espais en buit de l'escenari, es representen amb el caràcter ·.

Input Format

Primera línia:

• Dons nombres enters \(N\) i \(M\) que representen l'alt i l'amplte (respectivament) de la pantalla.

Següents línies:

• A cada línia, el contingut de cada casella de la matriu que representa la pantalla, on cada element es separa amb un espai.

Última línia:

• El caràcter (Unicode) \(D\) que representa la direcció en la que dispara la Samus, que pot ser:
  • ↑: la Samus dispara cap apunt.
  • →: la Samus dispara cap a la dreta.

Constraints

• \(N\) i \(M > 0\)
• \(M > N\)

Output Format

Cal dir que ha pasat amb el projectil que ha disparat la Samus, per exemple:

• La Samus ha disparat en línia recta cap a la dreta i ha impactat amb un obstacle.
• La Samus ha disparat en línia recta cap amunt i ha impactat amb un enemic.
• La Samus ha disparat en línia recta cap a la dreta i no ha impactat amb res.

Test Case 1

Input

3 8
· # · · · · · &
· · & · · # · ·
@ · · · · · · ·
→

Output

La Samus ha disparat en línia recta cap a la dreta i no ha impactat amb res.

Test Case 2

Input

3 8
· # · · · · · &
· · & · · # · ·
@ · · · · · · ·
↑

Output

La Samus ha disparat en línia recta cap amunt i no ha impactat amb res.

Test Case 3

Input

3 8
· # · · · · · &
· · & · · # · ·
@ · · # · · · ·
→

Output

La Samus ha disparat en línia recta cap a la dreta i ha impactat amb un obstacle.

Test Case 4

Input

3 8
· # · · · · · &
· · & · · # · ·
@ · · · · · · &
→

Output

La Samus ha disparat en línia recta cap a la dreta i ha impactat amb un enemic.

Test Case 5

Input

3 8
· # · · · · · &
· · & · · # · ·
@ · · # · & · ·
→

Output

La Samus ha disparat en línia recta cap a la dreta i ha impactat amb un obstacle.

Test Case 6

Input

3 8
· # · · · · · &
· · & · · # · ·
@ · · · · · & #
→

Output

La Samus ha disparat en línia recta cap a la dreta i ha impactat amb un enemic.

Test Case 7

Input

3 8
& # · · · · · &
· · & · · # · ·
@ · · # · · · ·
↑

Output

La Samus ha disparat en línia recta cap amunt i ha impactat amb un enemic.

Test Case 8

Input

3 8
# # · · · · · &
· · & · · # · ·
@ · · # · · · ·
↑

Output

La Samus ha disparat en línia recta cap amunt i ha impactat amb un obstacle.

Test Case 9

Input

5 8
· # · · · · · #
& · · · · · · ·
· # · · · · · &
# · & · · # · ·
@ · · # · · · ·
↑

Output

La Samus ha disparat en línia recta cap amunt i ha impactat amb un obstacle.

Test Case 10

Input

5 8
# # · · · · · #
& · · · · · · ·
· # · · · · · &
· · & · · # · ·
@ · · # · · · ·
↑

Output

La Samus ha disparat en línia recta cap amunt i ha impactat amb un enemic.

Test Case 11

Input

6 12
& · · · · · · · · # · ·
& · · · # · · · · · · &
# · · · · · & · · · · ·
· · # · · · · · · · · ·
· · · · · · · · # · · ·
@ & · · # # · · & · · #
↑

Output

La Samus ha disparat en línia recta cap amunt i ha impactat amb un obstacle.

Test Case 12

Input

6 12
& · · · · · · · · # · ·
# · · · # · · · · · · &
& · · · · · & · · · · ·
· · # · · · · · · · · ·
· · · · · · · · # · · ·
@ & · · # # · · & · · #
→

Output

La Samus ha disparat en línia recta cap a la dreta i ha impactat amb un enemic.

Test Case 13

Input

1 2
@ &
↑

Output

La Samus ha disparat en línia recta cap amunt i no ha impactat amb res.

Test Case 14

Input

1 2
@ &
→

Output

La Samus ha disparat en línia recta cap a la dreta i ha impactat amb un enemic.