33471번 - 대회 운영에 있어 제일 귀찮은 것은 무엇일까 서브태스크스페셜 저지

문제

에디토리얼이 해야 할 일이 많지는 않지만, 대회 종료 후에 해야 한다는 점에서 매우 귀찮다. 특히 대회 준비를 한 학기 이상 하는 MatKor Cup의 경우는 더더욱.

MatKor는 2022년 봄, 동수교(동우의 수학 교실)라는 이름으로 시작되었다. 이 당시에는 단순히 세미나만 진행하며 MatKor Cup 역시 에디토리얼 없이 세미나의 형태로 풀이를 설명하였다. 그러다 공개 대회로 전환하며 작성하게 된 에디토리얼은 동우에게 너무나 귀찮은 일이었다.

MatKor Cup의 경우 에디토리얼이 매우 늦게 나오는 것으로 유명하다. 각 출제자가 에디토리얼을 늦게 작성하지만, 특히 동우가 에디토리얼들을 합치는 과정은 매우 늦다. 이제 동우는 에디토리얼을 슬슬 써보려고 하는데 문자열 $S$를 작성하기가 너무 귀찮다! 동우는 최대한 타이핑을 줄이고 싶어 ctrl + a, ctrl + c를 한 번 해두고 ctrl + v를 계속 사용하고 싶다.

동우는 처음에 빈 문자열을 가지고 있고, $S$를 작성하기 위해 아래 행동을 할 수 있다.

• 행동 1: 현재 문자열 뒤에 원하는 문자 $c$를 입력하고, 1ドル$의 피로도가 쌓인다.
• 행동 2
  • 만약 문자열을 복사한 적이 없다면 ctrl + a, ctrl + c를 이용해 현재 문자열 전체를 복사한다.
  • 만약 문자열을 복사해 두었다면 현재 문자열 뒤에 복사해 둔 문자열을 ctrl + v를 이용해 붙여 넣는다.

동우의 피로도가 최소가 되도록 행동하고 싶고, 피로도가 최소가 되는 행동이 여러 가지 있다면 행동의 수를 최소화하고 싶다. 동우를 도와 이 방법을 찾아보자.

입력

첫 번째 줄에 알파벳 소문자로 이루어진 문자열 $S(1\le\lvert S\rvert\le 10^5)$이 주어진다.

출력

첫 번째 줄에 피로도의 최솟값 $P$와 피로도가 최소일 때 행동의 개수의 최솟값 $N$을 출력한다.

두 번째 줄에 $N$개의 문자로 이루어진 문자열을 출력한다. 이 문자열은 $P$개의 1과 $N-P$개의 2로 구성되어 있어야 하며, 문자의 순서대로 행동을 진행했을 때 $S$가 만들어져야 한다. 가능한 문자열이 여러 개라면 아무거나 하나 출력한다.

제한

서브태스크

힌트