Description
The game of "fool" is played with a small set of cards, which includes nine ranks - 6, 7, 8, 9, 0 (10), J (Jack), Q (Queen), K (King), A (Ace) of the four suits each - h (Hearts), s (Spades), d (Diamonds) and c (Crosses). So, for example a queen of spades is denoted Qs, and a ten of diamonds is 0d. One of the suits is declared a trump. During the game, the card beats another card, if either it has the same suit and higher rank, or it is a trump, while the beaten card is not.
In the game, a move proceeds as following. First player puts one of his cards on the desk, and the second player can either beat it with one of his cards, putting his card over it, or take it, if he has no suitable card. If the card is beaten, first player may flip in any of his remaining cards, which has same rank as any card already on the desk. This card, in turn, may be beaten or taken together with all other cards on the desk, etc. For example, if first player has cards 6s6dQhKd, the second player has 6h7h0sQd and hearts are the trumps, then first player can move with Kd, which is beaten with 6h, then flip in 6s, beaten by 0s, then 6d, beaten by Qd and at last Qh, which can not be beaten with 7h, so the second player has to take it.
Your task is to write a program that, given the trump suit and first and second player's cards, determines for the first player such a move as to eventually make the second player take.
If there is more than one such move, the program must find one with smallest rank. If there is several moves with smallest rank, program must choose the card with the first suit in the order mentioned in the first paragraph (i.e. h < s < d < c). In the example above, second player could beat Kd with 7h, thus preventing further flips. On the other hand, move of Qh will be immediately taken.
Input
In the first line of input file there is a single character h, s, d, or c, determining a trump suit. On the second line there is a string denoting first player's cards, and on the third line - the string with the second player's cards. All cards are different, and the players have equal number of cards.
Output
Output file must contain a single line with either a card to move or a string "NO", if a program was unable to find it.
Sample Input
s
As7h8dJc
Jd8s7c0c
Sample Output
7h
http://poj.org/problem?id=2542
