Card Trick

(1995 ACS Practice Problem U)

Write a program to perform this simple card trick:

  1. Give a pack of cards to a member of the audience.
  2. Have them cut the cards into two approximately equal piles and recombine the piles into one pack by shuffling them together.
  3. Repeat step 2 a few more times to ensure the cards are thoroughly shuffled.
  4. Without showing you, have them take the top card, remember which card it is, and replace it somewhere in the middle of the pack.
  5. Take back the pack and find which card was replaced in the middle of the pack. Show it to the audience to demonstrate your conjuring prowess!

To see how this amazing feat is performed, consider the pack ABCDEFGHIJKLMNOPQRST with 20 cards. Cutting and shuffling twice, then hiding the top card in the middle of the pack gives:

	Cut:				ABCDEFGHI     JKLMNOPQRST
	Shuffle:			JKALBCMDNEOPFGQRHSTI
	Cut:				JKALBCMDNE     OPFGQRHSTI
	Shuffle:			OJPFKALGBQCMRHDSNTEI
	Hide top card in middle:	JPFKALGBOQCMRHDSNTEI
If the initial order of the pack is known, cutting and shuffling k times produces 2 to the power of k interleaved sequences. Moving the top card produces 2k+1 (k is a power) sequences, one of which contains only one card. So taking out the JKLMN sequence leaves PFAGBQOCRHDSTEI. Taking out PQRST leaves FAGBOCHDEI. Taking out FGHI leaves ABOCDE and taking out ABCDE leave O. Whe know this is the card which was moved because there are 2k+1 (k is a power) sequences, and only one contains this card.

INPUT

Each line of the input is the order of cards in the pack after step 4 of the trick. The pack will contain between 4 and 52 cards and have been cut and shuffled between one and four times. Each card is represented by a single letter and the initial order of a full 52 card pack is ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz. Packs with n < 52 cards contain the first n of these beginning with A. The end of the input is indicated by a line containing only a #.

OUTPUT

For each pack of cards in the input, output a line of the form 

	The card was q.
if the chosen card can be determined or 
	I've failed.
if it cannot.


SAMPLE INPUT

BDEACFG
AEIBCHFGDJKL
JPFKALGBOQCMRHDSNTEI
OPQMDHIBJCFKEGNLRSAT
ABRCSDTEUFVGQWHXIYJZKaLbMcNdOePf
#

SAMPLE OUTPUT

The card was A.
I've failed.
The card was O.
I've failed.
The card was Q.

This problem was Practice Problem U in the 1995 ACS Australian Programming Competition.