Score : 900 points
Let x be a string of length at least 1.
We will call x a good string, if for any string y and any integer k (k \geq 2), the string obtained by concatenating k copies of y is different from x.
For example, a
, bbc
and cdcdc
are good strings, while aa
, bbbb
and cdcdcd
are not.
Let w be a string of length at least 1. For a sequence F=(\,f_1,\,f_2,\,...,\,f_m) consisting of m elements, we will call F a good representation of w, if the following conditions are both satisfied:
For example, when w=aabb
, there are five good representations of w:
aabb
)a
,abb
)aab
,b
)a
,ab
,b
)a
,a
,b
,b
)Among the good representations of w, the ones with the smallest number of elements are called the best representations of w.
For example, there are only one best representation of w=aabb
: (aabb
).
You are given a string w. Find the following:
(It is guaranteed that a good representation of w always exists.)
a
-z
).The input is given from Standard Input in the following format:
w
Print 2 lines.
aab
1 1
bcbc
2 3
b
,cbc
)bc
,bc
)bcb
,c
)ddd
3 1