0101. Prime Strings

Input file name:	primes.in
Output file name:	primes.out
Time limit:	2 s
Memory limit:	64 megabytes

The suffix of a string is its substring with first k symbols cut. Also the prefix of a string is its substring with last k symbols cut. One string is called lexicographically less than another if there exists their common prefix P, and the next symbol after this prefix in the first string is less than the corresponding symbol in second, or if P is equal to the first string but is not equal to second. For example, "a"<"ab", "aa"<"ab" but "abc">"abb".

The string is called prime if it is lexicographically less than all its suffixes. For example, strings "a", "abacade" and "dog" are prime, but the strings "baba", "abaa", "abacaba" and "kitten" are not.

You are given a string S. Your task is to find non-empty substrings of S: λ₁, λ₂, …, λ_t such that S is a concatenation of them S=λ₁+λ₂+…+λ_t, all λ_i are prime and λ₁ ≥ λ₂ ≥ …≥ λ_t, or determine that it is impossible.

Input file

The input file consists of only one string S. The length of the string does not exceed 1000000. The string is not empty. It is guaranteed that the string consists only of characters with ASCII codes from 33 to 126.

Output file

In the first line of the output write the number of substrings j. In subsequent j lines output the strings. If there are several solutions, output any of them. If there is no solution, output single number -1.

Examples:

primes.in	primes.out
kitten	3 k itt en

Source: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version