바보 게임

'바보' 게임은 다음 아홉 개의 끗수(rank)로 이루어진 작은 카드 묶음으로 진행한다: 6, 7, 8, 9, 0(10), J(잭), Q(퀸), K(킹), A(에이스). 각 끗수는 네 개의 무늬(suit)를 가진다: h(하트), s(스페이드), d(다이아몬드), c(클로버). 예를 들어 스페이드 퀸은 Qs, 다이아몬드 10은 0d로 표기한다.

무늬 하나가 으뜸패(trump)로 지정된다. 카드 X가 카드 Y를 "잡는다(beat)"는 것은 다음 두 조건 중 하나가 성립하는 경우를 말한다.

• X와 Y의 무늬가 같고 X의 끗수가 더 높다.
• X는 으뜸패이고 Y는 으뜸패가 아니다.

한 번의 공격은 다음과 같이 진행된다. 먼저 첫 번째 플레이어가 자신의 카드 한 장을 바닥에 낸다. 두 번째 플레이어는 자신의 카드 한 장으로 그 카드를 잡아 위에 덮거나, 잡을 수 있는 카드가 없으면 바닥의 카드를 모두 가져가야 한다. 카드가 잡히면, 첫 번째 플레이어는 바닥에 이미 놓인 어떤 카드와 끗수가 같은 카드를 자신의 남은 패에서 골라 추가로 낼 수 있다(이를 "얹기(flip in)"라 한다). 새로 낸 카드 역시 잡히거나, 잡지 못하면 바닥의 모든 카드와 함께 두 번째 플레이어가 가져가게 된다. 이 과정이 반복된다.

예를 들어 으뜸패가 하트일 때 첫 번째 플레이어의 패가 6s 6d Qh Kd, 두 번째 플레이어의 패가 6h 7h 0s Qd라고 하자. 첫 번째 플레이어가 Kd를 내면 6h로 잡히고, 이어서 6s를 얹으면 0s로 잡히고, 6d를 얹으면 Qd로 잡히며, 마지막으로 Qh를 얹으면 남은 7h로는 잡을 수 없어 두 번째 플레이어가 카드를 가져가게 된다.

당신의 과제는 으뜸패 무늬와 두 플레이어의 패가 주어졌을 때, 두 번째 플레이어가 결국 카드를 가져가도록 강제하는 첫 번째 플레이어의 첫 수를 찾는 프로그램을 작성하는 것이다. 두 번째 플레이어는 카드를 가져가지 않으려고 최선을 다해 방어한다고 가정한다.

그러한 수가 여러 개라면 끗수가 가장 낮은 것을 골라야 한다. 끗수가 가장 낮은 수가 여러 개라면 첫 문단에 나열된 무늬 순서(즉 h < s < d < c)에서 가장 앞선 무늬의 카드를 골라야 한다. 위 예에서 두 번째 플레이어는 Kd를 7h로 잡아 이후의 얹기를 막을 수 있으므로 Kd는 답이 될 수 없다. 반면 Qh를 내면 곧바로 가져가게 되므로 유효한 수이다.

첫째 줄에 으뜸패 무늬를 나타내는 문자 하나(h, s, d, c 중 하나)가 주어진다. 둘째 줄에는 첫 번째 플레이어의 패를, 셋째 줄에는 두 번째 플레이어의 패를 나타내는 문자열이 주어진다. 각 문자열은 카드들을 공백 없이 이어 붙인 것이다(카드 하나는 끗수 문자와 무늬 문자, 두 글자로 표기). 모든 카드는 서로 다르며, 두 플레이어의 카드 수는 같다.

두 번째 플레이어가 카드를 가져가도록 강제할 수 있는 첫 수 카드 하나를 한 줄에 출력한다. 그러한 수가 없으면 NO를 출력한다.