시간 제한
메모리 제한
시간 제한
1초
메모리 제한
128 MB
단어 찾기 퍼즐은 영어 소문자가 N행 N열로 놓인 표와, 표에서 찾아야 할 단어 목록으로 이루어진다.
퍼즐을 풀려면 목록의 각 단어가 표에 나타나는 모든 위치를 찾아야 한다. 단어는 어떤 칸에서든 시작할 수 있고, 위, 아래, 왼쪽, 오른쪽, 그리고 네 대각선 방향 중 하나로 일직선으로 놓일 수 있다. 단어가 한 번 발견될 때마다 그 단어를 이루는 모든 글자를 지운다.
모든 단어를 처리한 뒤, 지워지지 않은 글자를 행 우선 순서로 읽는다. 즉, 위쪽 행부터 아래쪽 행으로, 같은 행에서는 왼쪽에서 오른쪽으로 읽는다. 이렇게 얻은 문자열이 퍼즐의 정답이다.
주어진 퍼즐의 정답을 구하는 프로그램을 작성하라.
첫째 줄에 표의 크기인 정수 N (1 <= N <= 10)이 주어진다.
다음 N개 줄에는 표의 한 행을 나타내는 영어 소문자 N개가 주어진다.
그다음 줄에 단어 목록에 있는 단어의 수 R (1 <= R <= 100)이 주어진다.
다음 R개 줄에는 목록의 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 최대 10이다.
표의 모든 글자와 목록의 모든 단어는 영어 소문자 (a부터 z)로만 이루어져 있다.
퍼즐의 정답을 한 줄에 출력한다.
입력은 지워지지 않고 남는 글자가 적어도 하나 존재하도록 주어진다.