Lexicographically Smallest Decomposition with Rotations

Given an even-length string \( T \), your task is to find two strings \( A \) and \( B \), each of length \( \frac{|T|}{2} \), such that there exists an integer \( k \) (where \( 0 \leq k < \frac{|T|}{2} \)) satisfying:

[ \text{rotate}{left}(A,k)=A[k:]+A[:k], \quad \text{rotate}{right}(B,k)=B[-k:]+B[:-k] ]

and

[ \text{rotate}{left}(A,k)+\text{rotate}{right}(B,k)=T. ]

Among all such valid pairs \( (A,B) \), choose the one where \( A \) is lexicographically smallest. It is guaranteed that the string \( T \) always has a valid decomposition with \( k=0 \).

Note: All rotations are cyclic. For instance, if \( A = \texttt{abcd} \) and \( k = 1 \), then \( \text{rotate}_{left}(A,1) = \texttt{bcda} \); similarly, if \( B = \texttt{wxyz} \) and \( k = 1 \), then \( \text{rotate}_{right}(B,1) = \texttt{zwxy} \>.

inputFormat

The input consists of a single line containing the string \( T \). It is guaranteed that \( |T| \) is even.

outputFormat

Output two strings \( A \) and \( B \) separated by a single space, which represent the lexicographically smallest valid decomposition of \( T \) according to the problem conditions.

cdefabfabcde

cdefab fabcde