E. Guadalajara
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is a 100% true story that took place in 2024, during the first Latin American final.

Emanuel, from the team "teambrbr002", went to the airport in Belo Horizonte 10 hours in advance, where he would catch a flight to the city of Guadalajara, Mexico, for the first competition "Programmers of the Americas." After much conversation, problem-solving at the terminal, and a trip to Guarulhos, Emanuel heads to the immigration area when he encounters a terrible scene. Some evil being had swapped his passport for a work ID, both items being very similar, and now it is too late!

Emanuel manages to convince the airport staff to get a new ticket to Mexico, but it would be a long and lonely journey taking the route: SP -> MG -> home to get the passport -> SP -> Chile -> Panama -> Mexico.

Without internet and without his friends to talk to, Emanuel now only has some coins with him. He then decides to play an ancient game, passed down from generation to generation, which involves only a few coins — but can entertain (or trap) a player for countless hours.

Initially, the coins are placed in a row, some with heads (represented by the letter H) facing up, others with tails (represented by a T). In each turn, the player must:

  • Choose any coin that is heads (H) up and flip it (turning it to T);
  • For each coin to the left of the chosen one, he can individually decide whether to flip it or not.

After each turn, the player repeats the process with the new configuration of coins. The game ends when all the coins are tails (T) up, as there are no more possible moves.

But there is a legend that says that, depending on the initial configuration, the game can last forever, never reaching a final state.

Your task is to write a program that:

  • Detects if the game can be played infinitely. In this case, print only -1.
  • Otherwise, print the longest possible sequence of configurations of the coins after each valid move, including the initial state and the final state. If there are multiple maximum-length sequences, print any one of them.

Each configuration must be represented by a string of characters, containing only 'H' for heads and 'T' for tails, in uppercase letters.

Input

A single line with a string of up to 15 characters, representing the initial state of the coins. Each character will be 'H' or 'T'.

Output

If it is possible to play forever, print only $$$-1$$$. Otherwise, first print a line with an integer $$$k$$$, the number of elements in the maximum-length sequence. Then, print a line for each configuration in the sequence, starting with the initial state and ending with the state where all coins are turned to tails ('T'), one configuration per line. If there are multiple maximum-length sequences, print any one.

Examples
Input
HH
Output
4
HH
TH
HT
TT
Input
HTT
Output
2
HTT
TTT
Input
TTT
Output
1
TTT
Note

After a 3-day journey, Emanuel and his team were the champions of the competition, with a difference of only 1 minute from the second place.