ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1782. Jack's New Word

Time limit: 0.5 second
Memory limit: 64 MB
Jack is very laconical. He doesn't like to repeat the same thing several times. That is why the binary word which Jack has just written on a fence has no non-empty substrings of the form xyxyx, where x and y are (possibly empty) binary strings and the length of y doesn't exceed the length of x multiplied by two. For example, the Jack's word can't contain substrings 000 or 1001001 but can contain substrings 1010 and 001100110.
Fox Trot, who was passing by, asked Jack to describe the way he obtained his new word. Jack told him that first there was an empty word on a fence and then… The following story by Jack contains only phrases of the form:
  • “I prefixed the current word with 0 (or 1)”;
  • “I suffixed the current word with 0 (or 1)”;
  • “I replaced all zeroes with string 01, and all ones with string 10”.
Fox Trot is interested in that, but he will get bored after one hundred such phrases. Will Jack be able to finish his story?


The only input line contains a Jack's new word. This word is non-empty, consists of zeroes and ones and its length doesn't exceed 105.


If Jack has to say more than one hundred phrases to describe his word, output “−1”. In the other case output any possible description. The first line should contain a number of phrases k (1 ≤ k ≤ 100). The following k lines should describe these phrases in the order they should be pronounced. If a word should be prefixed with symbol c, output “front c”. If a word should be suffixed with symbol c, output “back c”. If all 0 should be replaced with 01 and all 1 should be replaced with 10, output “double”.


back 1
front 0
back 1


According to the story from sample output, Jack consecutively obtained: an empty string, “1”, “01”, “0110”, “01101001”, “011010011”.
Problem Author: Alex Samsonov
Problem Source: XV Open USU Championship