23564번 - 재귀 문자열 스페셜 저지

문제

길이가 $n$인 문자열 $S=s_1s_2\cdots s_n$와 길이가 $n$인 양의 정수 수열 $A=(a_1, a_2, \cdots a_n)$를 이용하여 다음과 같이 새로운 문자열 $T$를 만들 수 있다.

• $X_0$는 빈 문자열이다.
• $X_i = X_{i-1} s_i X_{i-1} s_i \cdots s_i X_{i-1},ドル $s_i$는 $a_i$번, $X_{i-1}$은 $a_i + 1$번 등장한다.
• $T = X_n$이다.

예를 들어 $S=abc$고, $A=(1,2,1)$이면 $X_1=a, X_2=ababa, X_3=T=ababacababa$가 된다.

$S$와 $A$를 이용하여 $T$를 만드는 것은 쉬우니, 반대로 $T$가 주어졌을 때 $T$를 만들어내는 $S$와 $A$를 찾아보자.

입력

문자열 $T$가 주어진다.

출력

첫 번째 줄에 $S$를 출력한다.

두 번째 줄에 $A$를 공백으로 구분하여 출력한다.

정답이 여러 개인 경우 아무 거나 한 가지만 출력한다.

제한

• $T$의 길이는 1 이상 2ドル^{20} = 1,048円,576円$ 미만이고, 알파벳 소문자로만 구성되어 있다.
• 조건을 만족하는 $S$와 $A$가 존재하는 입력만이 주어진다.

힌트