CAMELOT - Camelot

Camelot is a solitaire game that is played with a deck of French cards. The deck contains 52 cards, each of them having a suit and a face value. There are 4 possible suits and 13 possible face values. Since for this solitaire suits are not important, we consider that the deck contains 4 repetitions of each possible face value. Face values are A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q and K.

The solitaire starts with the full deck placed, face down, on the table. There is also a board containing 16 empty slots arranged in a 4 by 4 grid. The game repeatedly alternates two phases: a dealing phase and a removal phase. The first phase is a dealing phase. During this phase cards are dealt from the deck one at a time. Each card is placed, face up, in an empty slot. However, certain cards can only be placed in specific slots: Jacks (face value J) can only occupy the middle two slots of first and last columns. Queens (face value Q) can only occupy the middle two slots of first and last rows. Finally, Kings (face value K) can only occupy the corner slots. Cards having other face values can be placed in any empty slot. The game is lost whenever a card is dealt from the deck for which no valid empty slot exists. Each time the last empty slot has just been occupied, or when the deck is empty, a removal phase starts.

During a removal phase, it is possible to remove from the board any card or pair of cards that add up to 10. For this purpose, Aces (face value A) are considered as having value 1, while Jacks, Queens and Kings cannot be removed. For instance, it is possible to remove a 10 on its own, a pair formed by a 3 and a 7, a pair formed by an Ace and a 9, etcetera. Cards removed from the board are not used anymore during the game. The removal phase ends when no card can be removed from the board, or when the player decides not to continue removing cards. Notice that it is not mandatory to remove from the board every card that can be removed. However, since the player cannot decide the moment in which a new removal phase will begin, leaving removable cards on the board must be done carefully. Besides, note that if during a removal phase no card is removed, then the game is lost. When the removal phase ends, a new dealing phase starts, unless the deck is empty, in which case the game is over.

The game is won if the deck is empty and only Jacks, Queens and Kings are left on the board.

Camelot is really nice to play, but is frustrating to discover at the end of a game that it was impossible to win because of the initial arrangement of the deck. Even if the initial deck allows the player to win, he may fail to do so because of bad decisions or bad luck when placing or removing cards. Your job in this problem is to find out whether it is at least possible to win the game, given the order in which the cards will be dealt from the deck.

Input

Each test case is described using a single line. The line contains a single string of exactly 52 characters representing the initial arrangement of the deck. The first card dealt from the deck is given by the first character of the string, and so on. Each card is represented by its face value, with the exception of cards with face value 10 that are represented by the digit “0”. You may assume that the string corresponds to a valid initial arrangement of the deck, i.e., it contains exactly 4 repetitions of each possible face value. The end of input is indicated with a line containing a single asterisk (“*”).

Output

For each test case, output a single line containing an uppercase “Y” if it is possible to win the game with the given initial arrangement of the deck, or an uppercase “N” otherwise.

Example

Input:
AAAA222233334444555566667777888899990000JJJJQQQQKKKK
JJJJQQQQKKKKA9A9A9A928282828373737374646464655550000
JJJJQQQQKKKKA9A9A9A928282828333377774646464655550000
28333377774646464655550000JJJJQQQQKKKKA9A9A9A9282828
*

Output:
N
Y
N
Y

Added by:Pablo Ariel Heiber
Date:2010-09-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:FCEyN UBA ICPC Selection 2010

hide comments
2017-11-02 01:36:40
I love this type of problems, they appear tedious but never give me a hard time. My AC solution was produced in 50mins without a single test, and turned out to have just 1 small bug when finished. Coding such stuff in Python comes as natural as writing an email.
2010-09-27 23:22:17 Pablo Ariel Heiber
This solitaire is part of the Aisle Riot solitaire collection, in the Genome games package.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.