0101. Prime Strings

Имя входного файла:	primes.in
Имя выходного файла:	primes.out
Ограничение по времени:	2 s
Ограничение по памяти:	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

Источник: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати