The search engine company Elgoog has started to investigate alternative ways

to index data that would allow for large amounts of data to be queried more
cleverly than just about containing or not containing a substring. Working on this,
the researchers discovered a transformation that has many interesting properties.
They decided to call the transformation “shaking”.

Let’s consider a string S of length n (2 ≤ n ≤ 1000000) consisting of lowercase
Latin letters and the dollar sign ($). The latter is called a guard and has the code
less than that of any of the letters. The guard appears only once in the string, in
the last position. Then, for any integer k (1 ≤ k ≤ n-1, where k is a power of 2), we
define the shaken form of S as the string T obtained as follows:

1) For every cyclic shift of S write out the triple (PRK, POS, LAST), where PRK is
the first k characters of the shifted string, POS is the position (counting from
zero) of the first letter of S in the shifted string, and LAST is the last
character of the shifted string.

2) Sort the resulting triplets in ascending order , using the following rule to
compare the triples: for any two triples С1 = (PRK1, POS1, LAST1) and С2 =
(PRK2, POS2, LAST2) we will consider C1 < C2, if PRK1 is lexicographically less
than PRK2 or , if they are equal, if POS1 < POS2.

3) After sorting the triples, write out the values of LASTi in that order . This
sequence of letters is the shaken form T.
Let’s consider an example for k = 2:

S:

mississippi$

Shifts, and sorted triples:

mi ssissippi$ ($m, 11, i)

is sissippi$m (i$, 10, p)

ss issippi$mi (ip, 7, s)

si ssippi$mis (is, 1, m)

is sippi$miss (is, 4, s)

ss ippi$missi (mi, 0, $)

si ppi$missis (pi, 9, p)

ip pi$mississ (pp, 8, i)

pp i$mississi (si, 3, s)

pi $mississip (si, 6, s)

i$ mississipp (ss, 2, i)

$m ississippi (ss, 5, i)

T:

ipsms$pissii

The shaken form of a string usually has much simpler probabilistic structure

than the original, which allows quite complicated information about S to be
extracted from it using relatively simple algorithms. The researchers have
accomplished that, but now they have decided it would be a waste to keep both the
shaken T and the original S in the database. Using an automated theorem prover ,
they have learned that an efficient algorithm for extracting S from T must exist.
However , they have been unable to derive the algorithm and have turned to you
for help.