Problem B: The Burrow Wheeler Tranform

(Adapted from the MIUP’2011)

Burrow and Wheeler discovered in 1994 a clever but simple way to achieve very nice compression ratios when compressing blocks of data.

Basically, they propose a very simple procedure to pre-process the blocks to be compressed returning a convenient word that enables simple compression methods to be used that give good compresson rates.

Let us look at an example.

Imagine that you want to compress the word abracadabra. Burrow and Wheeler propose to compute the set of all the possible rotations (right to left rotations) of the word to be compressed. This gives:

0abracadabra
1bracadabraa
2racadabraab
3acadabraabr
4cadabraabra
5adabraabrac
6dabraabraca
7abraabracad
8braabracada
9raabracadab
10aabracadabr

Then they propose to order (using the natural lexicographic order) this list and to look at the word composed by the letters of the last column. The rotation set is now the following:

 

010aabracadabr
17abraabracad
20abracadabra
33acadabraabr
45adabraabrac
58braabracada
61bracadabraa
74cadabraabra
86dabraabraca
99raabracadab
102racadabraab

 
and the resulting rotated word is rdarcaaaabb.

Surprisingly enough this process tends to gather the same letters in the same part of the resulting word (and this then offers a very competitive compression ratio using very simple algorithms).

But more interesting is the following fact: there is an efficient way to recover the original word abacadabra by knowing only the word rdarcaaaabb and the position of the original word abacadabra in the rotation list that gave rdarcaaaabb, i.e. position 2.

Task

Your task is the following: compute this transformation.

Given a word, define a program that computes and gives the rotated word and the position in the ordered rotation list of the original word.

Input

The input consists of one line with the word to be compressed.

Constraints

The maximum size of a word to be compressed is 1000.

The ascii code of the input characters is exclusively included in the interval [33..126]. This constraint ensures that the given characters are human readable characters.

Output

The output consists of two lines.

The first line is the rotated word.

The second line contains the position (an integer) of the original word in the ordered rotation list.

Sample Input

abracadabra

Sample Output

rdarcaaaabb
2

This document was translated from LATEX by HEVEA.