Repeated Substrings in a Binary Signal

After watching the movie Contact, Little P was deeply moved and decided to dedicate his life to finding extraterrestrial signals. Every night he listens to his radio on the roof and records the noise as a binary string (composed of characters 0 and 1). Little P firmly believes that the alien message is hidden within this binary string in the form of repeated substrings.

Your task is to help him by finding all distinct substrings that appear more than once. In other words, for a given binary string s, you need to find every substring where its frequency of occurrence is greater than $$1$$.

If there are repeated substrings, output each repeated substring along with the number of times it occurs. The output should be sorted first by the length of the substring (in ascending order) and then lexicographically for substrings with equal length. If there is no repeated substring, output -1.

inputFormat

The input consists of a single line containing a binary string s (which contains only the characters '0' and '1'). The length of s is guaranteed to be small (for example, up to 100) so that a brute force solution is acceptable.

outputFormat

If there exist repeated substrings, for each such substring, output a line containing the substring followed by a space and its frequency. The substrings must be printed in the following order: firstly, in increasing order of length; secondly, lexicographically (i.e. dictionary order) if lengths are equal. If there is no repeated substring, output -1.

sample

001100

0 4
1 2
00 2