인쇄판

바이트란드의 한 인쇄소가 세로 줄무늬 벽지를 만들어 달라는 큰 주문을 받았다. 벽지 한 장은 폭이 같은 색 띠 $n$개가 나란히 놓인 모양이다. 주문한 쪽은 일부 띠의 색을 미리 정해 두었고, 나머지 띠의 색은 인쇄소가 마음대로 정해도 된다.

벽지를 찍을 때는 연속한 띠 여러 개를 한 번에 찍는 인쇄판을 쓴다. 인쇄판은 찍어 내는 띠마다 색이 정해져 있고, 길이가 벽지보다 짧아도 된다. 인쇄판의 길이가 $k$이면 인쇄판의 띠와 벽지의 띠가 정확히 맞물리는 위치 $n - k + 1$개 모두에 인쇄판을 대고, 그때마다 인쇄판의 띠를 전부 찍는다. 그래서 벽지의 한 띠가 두 번 이상 찍히기도 한다. 한 띠가 서로 다른 색으로 찍히면 그 띠의 최종 색은 찍힌 색이 섞인 색이 된다.

인쇄소는 벽지 전체를 찍어 낼 수 있는 인쇄판 중 가장 짧은 것을 설계하려고 한다. 주문한 쪽이 색을 정해 둔 띠는 다른 색이 섞이지 않은 순수한 색이어야 한다. 즉 그런 띠를 덮는 모든 인쇄판 위치에서, 그 띠 자리에 오는 인쇄판 띠의 색이 정해진 색과 정확히 같아야 한다.

첫째 줄에 벽지의 모양을 나타내는 문자열이 주어진다. 문자열은 라틴 알파벳 대문자와 별표(*)로 이루어진다. 서로 다른 대문자는 서로 다른 띠 색을 뜻하고, 별표는 주문한 쪽이 색을 정하지 않은 띠를 뜻한다. 문자열의 길이 $n$은 $1 \le n \le 1000000$을 만족한다.

원하는 벽지를 찍을 수 있는 인쇄판의 최소 길이 $k$를 한 줄에 출력한다.

벽지가 띠 7개짜리 A*B*B*A인 경우, 길이가 6인 인쇄판 ABBBBA로 이 벽지를 찍을 수 있다.