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

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?

Input

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.

Output

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”.

Sample

inputoutput
011010011
5
back 1
front 0
double
double
back 1

Notes

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