What is the most tedious part of running a contest?

The editorial does not have much work, but it is very tedious because it has to be done after the contest. This is especially true for MatKor Cup, which takes more than a semester to prepare.

MatKor began in spring 2022 under the name Donguisuhak (Dongu's math class). At that time it only held seminars, and MatKor Cup explained solutions in seminar form without an editorial. After it switched to an open contest, the editorial became extremely tedious work for Dongu.

MatKor Cup editorials are known for coming out very late. Each problem setter writes their editorial late, and Dongu's merging of the editorials is slower still. Now Dongu wants to start writing the editorial, but typing the string $S$ is too tedious! To minimize typing, Dongu wants to press ctrl + a and ctrl + c once, then keep using ctrl + v.

Dongu starts with an empty string. To write $S$, Dongu can perform the following actions.

• Action 1: Type the character $c$ after the current string. This adds 1 to the fatigue.
• Action 2
  • If the string has not been copied yet, copy the entire current string with ctrl + a, ctrl + c.
  • If the string has already been copied, paste the copied string after the current string with ctrl + v.

Dongu wants the fatigue to be as small as possible. If several action sequences reach the minimum fatigue, Dongu wants the fewest actions. Help Dongu find such a sequence.

The first line contains a string $S$ of lowercase English letters ($1\le\lvert S\rvert\le 10^5$).

The first line prints the minimum fatigue $P$ and the minimum number of actions $N$ among sequences with minimum fatigue.

The second line prints a string of $N$ characters made of $P$ 1s and $N-P$ 2s. Performing the actions in this order must produce $S$. If several strings are possible, print any one of them.