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
1001001 but can contain substrings
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
“I suffixed the current word with
“I replaced all zeroes with string
01, and all ones with string
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”.
0 should be replaced with
01 and all
1 should be replaced with
10, output “double”.
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