대회 운영에 있어 제일 귀찮은 것은 무엇일까

에디토리얼이 해야 할 일이 많지는 않지만, 대회가 끝난 뒤에 해야 해서 매우 귀찮다. 특히 한 학기 넘게 준비하는 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$가 만들어져야 한다. 가능한 문자열이 여러 개라면 아무거나 하나 출력한다.