War

In many places, the card game “war” is popular amongst children. As we shall see, the game result completely depends on the initial distribution of cards between two players, A and B. We consider a standard 32 card game and we ignore suits, only ranks are important. Hence we have 4 × 8 cards: seven (7), eight (8), nine (9), ten (T), jack (J), queen (Q), king (K) and ace (A) — ace being thestrongestcardandseventheweakest,i.e. 7<8<9<T<J<Q<K<A. At game start, players each hold a deck of 16 cards in their hand, face down. The object of the game is to win all the cards. Both players now turn their top card face up and put it on the table. Whoever plays the higher card takes both cards and adds them (face down) to the bottom of his or her deck. It is important to notice that the higher, winning, card is added first. Then both players turn over their next card, and so on. If the turned over cards are equal there is a war. The tied cards stay on the table and both players play the next card of their deck. Whoever has the higher of the new face-up cards wins the war and adds all four cards face-down to the bottom of his or her deck. If the new face-up cards are equal as well, the war continues: each player puts another card face-up. The war goes on like this as long as the face-up cards continue to be equal. As soon as they are different the player of the higher card wins all the cards in the war and add those cards to the bottom of his or her deck. The higher, winning, card is added first, then the lower card, then all the tied card in reverse playing order. For instance, let us assume that players A and B have the following decks (the deck of player A is shown first and top of decks at left): AKKQQJJTT998877A AK7QQJJTT99887KA A war is started because both A and B play aces, then the war goes on because of kings, and finally player A’s king wins over player B’s seven. Hence, player A collects all cards on the table. Now, the decks are as follows: QQJJTT998877AK7KKAA QQJJTT99887KA As regards the outcome of the whole game there are four situations:

1. Player A wins the game when player B’s deck becomes empty while player A still owns cards. 2. Player B wins the game in the symmetric situation.
2. There is a draw, when both players exhaust their cards simultaneously.
3. The game lasts forever. Write a program that computes the outcome of the game from the initial decks of players A and B. Input The input file contains several test cases, each of them is made of two lines: the first line is player A’s deck, while the second line is player B’s deck.

2/2 Output For each test case, your program must output one line, which should be ‘A wins’, ‘B wins’, ‘draw game’ or ‘play forever’, depending on the game’s outcome. Sample Input AKKQQJJTT998877A AK7QQJJTT99887KA AAKKQQJJTT998877 AAKKQQJJTT998877 87TT8799QJAAQJKK T8T79897AQAJKQKJ Sample Output A wins draw game play forever