Car Plates Competition

Martin and Isa are very competitive. Their newest competition is about spotting the plates of cars on the street. Each time one of them sees a car plate, they send the other an SMS message with the plate; whoever has seen the newest plate is in the lead. Because the Automobile Car Management (ACM) office assigns plates sequentially in increasing order, they can compare the plates and decide who is winning.

Martin has a very sharp eye and has stayed in the lead for weeks. Isa, tired of always being behind, wrote a program that generates a random plate, so that the next time Martin sends her a message she can reply with the generated plate and give him a hard time.

Martin has grown suspicious and wants to decide whether Isa really saw a car with the plate she sent. He knows several facts about how the ACM assigns plates:

• Each plate is a combination of 7 characters, each of which may be an uppercase letter (A-Z) or a digit (0-9).
• There are two plate schemes: the old one, used for years, and the new one, in use for a few months, introduced once the old combinations were exhausted.
• In the old scheme the first three characters are letters and the last four are digits, so plates run from AAA0000 to ZZZ9999.
• In the new scheme the first five characters are letters and the last two are digits. However, the printer cannot print the letters A, C, M, I, and P, so the first plate of the new scheme is BBBBB00 instead of AAAAA00.
• Plates are assigned in sequential order. In particular, the last plate of the old scheme is immediately followed by the first plate of the new scheme.

Isa is unaware of all this. Her random generator only guarantees that the plate has seven characters where the first three are uppercase letters, the last two are digits, and each of the fourth and fifth characters is either an uppercase letter or a digit (possibly producing an illegal combination).

Martin will not consider Isa the winner if he receives an illegal combination, or a legal plate that is equal to or older than his. Moreover, since new plates are not produced very fast, he will not believe Isa saw a plate that is newer than his but sequentially too far ahead. For example, if Martin sends DDDDD45 and receives ZZZZZ45, he will not believe it, because the ACM could not have printed that many plates in the meantime.

Therefore Martin considers Isa the winner only if he receives a legal plate that is newer than his and older than or equal to the $C$-th consecutive plate after the one he sent. He calls $C$ his confidence number. For example, if Martin sends ABC1234 with confidence number $6$, he considers Isa the winner only if the received plate is newer than ABC1234 and older than or equal to ABC1240.

The input contains several test cases. Each test case is a single line with two strings $S_M$ and $S_I$ and an integer $C$, separated by single spaces. $S_M$ is the 7-character plate sent by Martin, which is always a legal plate. $S_I$ is the 7-character string returned by Isa, produced by her random generator. $C$ is Martin's confidence number ($1 \le C \le 10^9$).

The end of the input is indicated by a line with $S_M = S_I =$ * and $C = 0$, which must not be processed.

For each test case, print a single line containing the uppercase letter Y if, according to Martin, Isa is the winner, or the uppercase letter N otherwise.