아나드롬 분할

팰린드롬은 왼쪽에서 읽으나 오른쪽에서 읽으나 똑같은 단어다. "kisik"과 "abba"가 팰린드롬이다.

한 단어의 글자 순서만 바꿔서 다른 단어를 만들 수 있으면 두 단어는 애너그램이다. 예를 들어 "kanonada"와 "anakonda"는 애너그램이다.

어떤 팰린드롬의 애너그램인 단어를 아나드롬이라고 한다. "p", "abab", "sikki"는 아나드롬이지만 "papagaj"와 "anakonda"는 아나드롬이 아니다.

모든 단어는 아나드롬인 부분 단어(원래 단어에서 연속한 글자를 잘라낸 문자열)로 쪼갤 수 있다. 단어가 주어지면 조각 수가 가장 적은 분할을 찾아라.

첫째 줄에 영어 소문자로 이루어진 단어가 주어진다. 단어의 길이는 1 이상 10000 이하다.

첫째 줄에 조각을 공백 하나로 구분해 출력한다. 출력은 다음 조건을 모두 만족해야 한다.

• 조각을 순서대로 이어 붙이면 입력 단어가 된다.
• 각 조각은 아나드롬이다.
• 조각 수가 최소다.

세 조건을 만족하는 분할이 여러 개이면, 출력하는 줄 전체가 사전순으로 가장 앞서는 분할 하나만 출력한다. 공백은 어떤 소문자보다도 앞선다고 본다. 다시 말해 조각을 왼쪽부터 정하면서, 남은 부분을 남은 조각 수로 계속 쪼갤 수 있는 한 각 조각을 최대한 짧게 자르면 된다.