당신은 정말 우연히 발을 헛디뎌 그만 algowiki 미로에 갇혀버렸다. 주위를 둘러보니 낡은 글귀가 쓰여져 있었는데, 이는 다음과 같다.

• 이곳은 $N \times M$개의 칸으로 구성된 직사각형 미로이다.
• 미로는 자유롭게 지나다닐 수 있는 공간, 벽, 플래그, 당신의 처음 위치, 탈출구로 구성된다.
• 벽은 지나다닐 수 없다.
• 플래그는 'a', 'l', 'g', 'o', 'w', 'i', 'k', 'i'로 총 $8$개이다.
• 상하좌우로 인접한 칸에 대해 한 칸씩 자유롭게 이동할 수 있으며, 각 이동 당 $1$의 단위 시간이 걸린다.
• 당신은 $8$개의 플래그를 모두 획득하여 탈출구로 이동해야만 탈출할 수 있다.
• 플래그를 모두 획득한 뒤 탈출구에 도착하면 그 즉시 탈출에 성공한다.

첫째 줄에 $N, M$이 공백으로 구분되어 주어진다. $(1 ≤ n, m ≤ 50; 10 ≤ n \times m)$

둘째 줄부터 $N$개의 줄에 걸쳐 길이 $M$의 문자열 형태로 미로의 모습이 주어진다. 벽은 'X'로, 자유롭게 지나다닐 수 있는 공간은 'O'로 표현된다.

플래그는 본문에 정의된 알파벳과 같고 당신의 처음 위치는 'S', 탈출구는 'E'로 표현된다.

플래그 $8$개와 'S', 'E'는 반드시 주어진다.