Decoding a cyclic shift of a string with a repeating pattern

Kotlin Hard strings

Task «Decoding a cyclic shift of a string with a repeating pattern»

Given an encoded string obtained from the original string by cyclically shifting it left by some number K (0 ≤ K < length of the string) and then replacing each character with its ASCII code written in decimal. The original string consists only of lowercase Latin letters (a-z) and has a length of no more than 1000. It is known that the original string is the result of repeatedly repeating some pattern of length P (1 ≤ P ≤ length of the string) — i.e., the string has the form S = T + T + ... + T (an integer number of times). It is necessary to find the length of the minimum possible pattern P and restore the original string before the cyclic shift. If there are several possible original strings, choose the one that is lexicographically smallest (in its original, unshifted form). Input data: a single line containing a sequence of integers separated by spaces — this is the encoded string. The length of the sequence is L (1 ≤ L ≤ 2000). Output data: two numbers — the length of the minimum pattern P and the shift value K, followed on the next line by the restored original string (before the shift). If restoration is impossible, output -1.

Input Format

One line containing integers separated by spaces — the character codes of the encoded string.

Output Format

In the first line, two integers: P and K. In the second line — the original string before the shift. If no solution is found, output -1.

Examples

Example 1

INPUT

99 97 98 99 97 98

OUTPUT

3 1
abcabc

Example 2

INPUT

97 98 97 98

OUTPUT

2 0
abab

main.kt