퍼즐 같은 문제

문제

애나 그레이엄(Anna Graham)은 자기 작품의 완성도와 복잡함에 자부심을 가진 퍼즐 제작자다. 그녀는 크로스워드, 논리 퍼즐, 아크로스틱, 단어 찾기 등 온갖 종류의 퍼즐을 만든다. 퍼즐 종류마다 스스로 지키는 규칙을 정해 두었다.

단어 찾기 퍼즐에서는 (대부분의 단어 찾기처럼) 모든 단어가 서로 연결되어 있어야 할 뿐 아니라, 단어 목록에서 어떤 단어 하나를 빼더라도 남은 단어들 중 어느 하나도 나머지와 끊어지지 않아야 한다. 보통의 단어 찾기처럼 각 단어는 격자에서 여덟 방향(가로, 세로, 대각선 중 하나로 정방향 또는 역방향) 중 한 방향으로 일직선을 이루는 칸들에 놓이며, 두 단어는 그 직선이 공통의 칸을 지날 때 서로 연결된 것으로 본다. 예를 들어 아래 두 예제 퍼즐 중 첫 번째는 이 조건을 만족하지만 두 번째는 그렇지 않다. 두 번째에서는 단어 Pascal을 빼면 Java가 나머지 단어들과 끊어진다.

애나의 단어 찾기 퍼즐이 그녀의 기준을 만족하는지 검사하는 프로그램을 작성하는 것이 여러분의 과제다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $n$, $m$, $l$이 주어지는데, $n$과 $m$은 퍼즐 격자의 행과 열의 수이고 $l$은 단어의 수이다. 이어서 $m$개의 대문자로 이루어진 $n$개의 줄(격자)이 오고, 그다음 한 줄에 하나씩 $l$개의 단어(대소문자가 섞인 단어 목록)가 온다. 목록의 각 단어는 퍼즐에 정확히 한 번 나타난다. 격자의 행은 최대 100개, 열은 최대 100개이며, 단어는 최대 100개이다. 입력 단어에는 공백이 없다. $n = m = l = 0$인 줄은 입력의 끝을 의미한다.

출력

각 테스트 케이스마다, 퍼즐이 애나의 조건을 만족하면 Yes, 그렇지 않으면 No를 한 줄에 출력한다.

힌트

보너스 퍼즐 (시간이 조금 남는 분들을 위해).

A D N E R H E B E T W E S T M I N S T E R T H
Y E G R A V E M E U D R U P O B E R L I N D E
E C M I C H I G A N W A T E R L O O I G I N T
L G E M R C U N T D I V E L L I V R A D E C A
L E U A H R W S E I E B T T Y S N T H R E S T
A R E I I I B N V Y O R K O S A A G A L N O S
V K G M N T O A I W H F T R G G G Z A E R I T
D A R D O M U D L E I H T O N I A D E R N B H
N R S O A Y E I O D O A T N N N K U D D B I G
A O L R N N N R G R W S I T N A Q E I S E O I
R A I R C G C E H G E I P O O W I A N N G N R
G H P O G I N H H N S I N F T V N T B H E A W
M S P R T U N S O G L R D W E A O N O T S G M
U A E N F D A C L R E I R U A L D I R F L I W
G E R O L B U E I V Y L H M E L I A O N C H D
N T Y I H O O Q T N A U L D G E L H Y H T C H
I E R H E T Y M U M N A O A A Y Y A I T E I B
K W O O S T E R N E W A H S N A F G C D O M R
S U C P I A T N A B S I T M C M A S T E R N O
U G K H O W L A U R E N T I A N O T E L R A C
M A S H L A N D Y T I C E V O R G L E J P B K

ALMA			DAYTON			MICHIGAN		SHERIDAN
AKRON			DUQUESNE		MT VERNON NAZARENE	SLIPPERY ROCK
ALLEGHENY		EDINBORO		MUSKINGUM		SPRING ARBOR
ASHLAND 		E(astern) MICHIGAN	N(orthern) MICHIGAN	THIEL
BALDWIN-WALLACE		FANSHAWE		NOTRE DAME		TOLEDO
BEHREND			GRAND VALLEY		OBERLIN			TORONTO
BOWLING GREEN		GROVE CITY		OHIO N(orthern)		WATERLOO
BROCK			HIRAM			OHIO WESLEYAN		WESTMINSTER
CARLETON		IIT			OLIVET			WILFRID LAURIER
CEDARVILLE		INDIANA			OTTAWA			WINDSOR
CINCINNATI		LAURENTIAN		PITT			WOOSTER
C(entral) MICHIGAN	MARIETTA		PURDUE			WRIGHT STATE
CMU			MCMASTER		QUEENS			YORK
CONESTOGA		MIAMI			SAGINAW VALLEY