지질 지층

시간 여행은 까다로운 일이다. 가끔은 의도한 시점에서 수억 년이나 벗어난 곳에 도착하기도 한다. 그래서 시간 여행 외판원 팀(Tim)은 자신이 목표한 시대 근처에 제대로 도착했는지 확인하고 싶어 한다. 미래로 갈 때는 주변에 물어볼 사람이 늘 있으니 쉽다. 하지만 과거로 갈 때는 사정이 다르다. 인류가 존재한 기간 자체가 짧고, 달력으로 시간을 기록한 역사는 더더욱 짧기 때문이다. 먼 과거로 이동하는 경우를 위해, 팀은 자신이 도착한 시대를 확인할 새로운 방법을 고안하려 한다.

한 가지 방법은 지질 연대 측정의 원리를 이용하는 것이다. 팀은 도착한 곳에서 땅의 코어 시료(원기둥 모양으로 뽑아낸 표본)를 채취해, 지층(strata)이라 불리는 퇴적층들을 관찰할 수 있다. 각 지층은 특정 지질 시대에 형성되었다. 서로 다른 지층을 구분하기는 쉽지만, 지역마다 기후와 토양 구조가 달라서 퇴적물만으로는 그 지층이 어느 지질 시대에 속하는지 알 수 없다. 이때 화석이 실마리가 된다. 어떤 지층에 화석이 들어 있으면, 그 화석 기록과 '한 종의 모든 개체는 같은 지질 시대에 살았다'는 사실에 근거하여 해당 지층의 지질 시대를 알 수 있다. 따라서 팀이 도착한 시대를 확인하려면, 코어 시료의 지층들이 그가 타임머신에 입력한 목표 시대와 앞뒤가 맞는지만 판단하면 된다.

첫 줄에는 테스트 케이스의 수 $K$가 주어진다. 이어서 $K$개의 테스트 케이스가 다음 형식으로 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $t$, $w$, $d$가 주어진다. $t$는 팀의 목표 시대(단위: 백만 년 전), $w$와 $d$는 각각 코어 시료의 너비와 깊이이며 $0 \le t \le 3000$, $1 \le w, d \le 100$이다. 다음 $d$개의 줄에는 각각 $w$개의 문자가 있으며 코어 시료를 나타낸다. 각 문자는 숫자(0–9) 또는 대문자(A–M)이다.

숫자는 특정 지층에 속한 퇴적물을 뜻한다. 지층 0은 지표면이므로 팀의 목표 시대의 지질 시대와 일치한다. 지층 1은 지층 0 바로 아래층, 지층 2는 지층 1 바로 아래층이며, 이런 식으로 아래로 내려간다. 즉 한 층 깊어질 때마다 바로 위층보다 지질 시대가 한 시대씩 더 오래되었다.

대문자는 화석이며, 그 이름표는 아래 표에 따라 지질 시대를 나타낸다.

화석은 자신을 둘러싼 지층에 속한다. 이때 대각선을 포함한 여덟 방향의 이웃 칸을 모두 본다. 어떤 화석이 두 종류 이상의 지층에 접해 있으면(예: 1과 2 모두), 숫자가 가장 작은 지층에 속하는 것으로 본다. 어떤 화석도 다른 화석에만 완전히 둘러싸여 있지는 않으며, 모든 코어 시료에는 화석이 적어도 하나, 지층이 적어도 하나 존재한다.

각 테스트 케이스마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 다음 줄에는 코어 시료의 모든 화석이 팀의 목표 시대와 앞뒤가 맞으면 Yes를, 그렇지 않으면 No를 출력한다. 연속한 테스트 케이스 사이에는 빈 줄을 하나 넣어 구분한다.