우주에서 길을 잃다

이 프로그램은 N x N 문자 배열에서 문자열을 찾아야 한다. 이 문제에서 "문자"란 출력 가능한 모든 ASCII 문자(ASCII 값 32부터 126까지)를 말한다.

입력은 다음과 같이 구성된다.

• 1번째 줄: N의 값 (N <= 50),
• 2번째 줄부터 N+1번째 줄까지: 길이가 N인 문자열. 공백을 포함할 수 있다. (단, 일부 PC 편집기가 뒤쪽 공백을 자동으로 잘라내므로 SPACE.IN 파일의 어떤 줄에도 뒤쪽 공백이 없다. 즉, 모든 줄은 공백이 아닌 문자로 끝난다. 앞쪽 공백과 중간 공백은 허용된다.)
• N+2번째 줄부터 파일 끝까지: 길이가 1 이상 N 이하인 문자열. 공백을 포함하지 않는다.

파일의 2번째 줄부터 N+1번째 줄까지는 N x N 배열의 내용을 나타낸다. 2번째 줄이 1행, 3번째 줄이 2행인 식이다.

N+2번째 줄부터는 각 문자열이 배열에서 나타나는 모든 위치를 찾아야 한다. "나타난다"란 문자열의 첫 문자가 그 위치의 문자와 일치하고, 문자열의 이후 문자들이 배열에서 공백을 건너뛰면서 여덟 가지 방향 E(오른쪽), NE(오른쪽 위 대각선), N(위), NW(왼쪽 위 대각선), W(왼쪽), SW(왼쪽 아래 대각선), S(아래), SE(오른쪽 아래 대각선) 중 하나로 배열의 문자와 일치한다는 뜻이다. 찾는 문자열은 배열의 한쪽 가장자리에서 다른 쪽 가장자리로 "넘어갈" 수 없다.

각 문자열에 대한 출력은 다음과 같다.

• 문자열 자체
• "not found"라는 메시지 또는 문자열이 발견된 모든 시작 위치와 방향을 (행,열) - 방향 형식으로 나열한 목록 [예: (5,3) - NW]
• 빈 줄

문자열이 두 번 이상 나타나면 각 발생을 모두 보고해야 한다. 여러 발생을 보고하는 순서는 중요하지 않다.