시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 512 MB139292524.272%

문제

밤이 되면 어두워지는 다솔관에는 좀비가 나온다는 괴담이 있다. 그 좀비들의 정체는 바로 시험 기간에 공부하느라 지친 학생들이었다. 지친 학생들은 멀리서 보면 흡사 좀비이므로 학생 좀비라고 부르자. 아리는 낮에 공부하다가 깜빡하고 책을 두고 와서 밤에 다시 다솔관 4층으로 가야 한다. 밤에 다솔관 4층에 도착한 아리는 겁이 많아서 학생 좀비들을 마주친다면 기절해버리고 말 것이다. 아리는 기절 하지 않고 무사히 책을 찾아 돌아가고 싶다.

N × N으로 이루어진 다솔관 4층 곳곳에는 형광등 스위치와 학생 좀비들이 있다. 아리는 가장 왼쪽 위인 (1, 1)에서 출발하고 아리와 학생 좀비들은 모두 아래 방향을 보고 있다. 아리는 주어진 순서 A에 따라 이동을 한다. 문자열 AF, L, R로 구성되어 있으며, F는 앞으로 1칸 전진, L은 아리가 현재 바라보고 있는 방향을 기준으로 왼쪽으로 90도 방향 전환, R은 오른쪽으로 90도 방향을 전환한다. 다솔관 4층 주변에는 벽이 있어서 N × N 밖으로는 이동할 수 없다. 벽에 부딪히게 되면 전진하지 못하고 제자리에 머문다.

밤에는 학생들이 별로 없어서, 다솔관 4층은 암전 상태이다. 겁이 많은 아리는 형광등 스위치가 있는 칸에 도착하면 그 곳에 학생 좀비가 있더라도 학생 좀비랑 마주치기 전에 스위치를 켠다. 스위치를 켜게 되면 해당 스위치가 있는 칸과 상, 하, 좌, 우, 대각선 네 방향으로 1칸씩 불을 밝힌다. 스위치는 한 번 켜게 되면 꺼지지 않는다. 아리가 이동을 마칠 때마다 학생 좀비들은 자신이 보고 있는 방향으로 한 칸 전진한다. 만약 학생 좀비들이 벽에 부딪히게 되면 제자리에서 뒤를 돌아 반대 방향을 바라본다.

아리는 불이 꺼져있는 칸에서 학생 좀비와 함께 있으면 괴담에서 나오는 좀비로 착각하여 그 자리에서 바로 기절해 다음 날 아침에 깨어난다. 하지만 불이 켜져 있는 칸이거나 스위치가 있는 칸에서는 평범한 학생인 것을 알아보고 기절하지 않는다.

아리는 어두워진 다솔관에서 사물함을 찾아 이동하는 중이다. 이동 중에 기절하지 않을 수 있는지 구하여라.

입력

첫째 줄에 한 개의 정수 N(10 ≤ N ≤ 15)이 주어진다.

다음 줄에는 아리가 이동할 순서 문자열 A(10 ≤ A의 길이 ≤ 50)가 주어진다.

다음 줄부터 N × N의 다솔관 지도가 주어진다. 'Z'는 학생 좀비(0 ≤ 학생 좀비의 수 ≤ N × 2)를 나타내고 'S'는 형광등 스위치(0 ≤ 형광등 스위치의 수 ≤ N × 2)를 나타낸다. 'O'는 아무것도 없는 빈칸이다. 아리가 처음에 위치한 (1, 1)은 항상 빈칸인 경우만 입력으로 주어진다.

출력

아리가 기절을 하게 된다면 "Aaaaaah!"를 출력하고, 기절을 하지 않는다면 "Phew..."를 출력하시오.

예제 입력 1

11
FFFFFFRLRL
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
SOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
ZOOOOOOOOOO

예제 출력 1

Phew...

예제 입력 2

11
FFFFFFRLRL
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
OOOOOOOOOOO
ZOOOOOOOOOO

예제 출력 2

Aaaaaah!