OpenKattis
National University of Singapore

Trash

/problems/trash/file/statement/en/img-0001.png
A game of Trash in progress.

From her friends, Theta learned a $2$-player card game called Trash. Trash is played with a standard $52$-card deck consisting of Ace, $2$ to $10$, Jack, Queen, and King in each of the $4$ suits. Each player is dealt $10$ cards face down that are arranged in $2$ rows for each player as shown in the figure. The first row represents slots for an ace, a $2$, a $3$, a $4$, and a $5$ of any suit, the second row represents slots for $6$, $7$, $8$, $9$, $10$ of any suit. The first player who can fill all $10$ of their slots with a card of the appropriate kind wins.

Players take turns to play Trash. At the beginning of each turn, a player draws from the drawing pile, which initially contains all cards that have not been dealt face-down. If the player can use the card drawn to fill one of their slots that has not been filled, they uncover and remove the face-down card from the slot and put the drawn card face up in the slot. Then, the player repeats their turn with the card uncovered (instead of drawing a new card from the drawing pile) until they either fill all slots or uncover a card that cannot fill a slot.

If a player draws or uncovers a card that cannot fill any slot (such as a Queen or King), or if a player draws or uncovers a card that corresponds to a slot they’ve already filled, that card is put on the discard pile and the player loses their turn. Then, the other player takes their turn or turns by first drawing from the drawing pile, then placing cards as long as they fill slots. Note that in this version of Trash, a player may never take any cards from the discard pile. Whichever player first fills all of their slots wins.

A special case is the Jack, which acts as a wildcard. Whenever a player draws (or uncovers) a Jack, they can use the Jack to fill any of their remaining slots.

Theta quickly discovers that it matters how you use any Jacks you draw, namely so that you minimize the chance of being left with an unfilled slot. If there are multiple optimal choices for slots in which to place a Jack, she chooses the lowest-numbered slot (Ace counts as $1$). Most of her friends, however, use a simpler strategy of always using their Jacks to fill the lowest-numbered unfilled slot, regardless of which cards were already placed or discarded.

Write a program that determines who wins in a game between Theta and one of her friends! Note that Theta bases her decision on only those cards that are turned face-up in a slot and the cards that have been discarded onto the discard pile, but not the face-down cards or the cards remaining in the drawing pile.

Input

Input consists of a single string denoting the shuffled deck, which consists of $52$ characters, with each of A, J, Q, K, 2, 3, 4, 5, 6, 7, 8, 9, and T appearing exactly $4$ times. Since the suit of a card does not matter for the game, it is not given in the input. 2 - 9 stand for cards $2$ to $9$, T stands for $10$, and A, J, Q, and K stand for Ace, Jack, Queen, and King.

The first $10$ cards in the deck are dealt face-down to Theta, with the first card in her Ace/$1$ slot, the second card in her $2$ slot, and so on. The next $10$ cards are dealt to her friend, with the $11^{\texttt{th}}$ in the Ace/$1$ slot, and so on. The $21^{\texttt{st}}$ card in the deck is the first card drawn. Neither player is allowed to look at their face-down cards. Theta starts the game.

You are guaranteed that one player will be able to win before the deck runs out of cards.

Output

If Theta wins this game with her strategy, output “Theta wins”. Otherwise, output “Theta loses”. Do not add a period to the output.

Sample Input 1 Sample Output 1
23456789TJ23456789TJA89Q66JK37T2A4AQK3AK5T8Q24K97JQ5
Theta wins
Sample Input 2 Sample Output 2
89724TJTA67K4J87Q8T6Q7J2324T558KA99A3KA356QJ6523QK49
Theta wins
Sample Input 3 Sample Output 3
6Q4K476722745A9A9875A2TT3JA6K5K34JKQQTQ235T9868J893J
Theta loses