Cắt xâu thành các đoạn đối xứng

Một xâu là đối xứng (palindrome) nếu đọc từ trái sang phải hay từ phải sang trái đều cho cùng một kết quả, ví dụ madam, civic, a.

Cho xâu \(S\). Ta có thể cắt \(S\) tại một số vị trí (có thể không cắt) để chia thành các đoạn liên tiếp. Hãy liệt kê mọi cách cắt sao cho mọi đoạn thu được đều là xâu đối xứng.

Input

Một dòng duy nhất chứa xâu \(S\) gồm các chữ cái Latinh thường.

Output

In mỗi cách cắt trên một dòng: các đoạn theo thứ tự từ trái sang phải, cách nhau đúng một dấu cách. Các cách cắt được in theo thứ tự sau: so sánh hai cách cắt từ trái sang phải, đoạn đầu tiên nào ngắn hơn thì cách cắt đó đứng trước (nếu hai đoạn đầu bằng nhau thì so sánh tiếp đoạn thứ hai, v.v.).

Constraints

• \(1 \le |S| \le 30\), \(S\) gồm chữ cái thường a-z.
• Để kết quả không quá lớn, đảm bảo số cách cắt hợp lệ không vượt quá \(10^5\).

Sample Input 1

civicab

Sample Output 1

c i v i c a b
c ivi c a b
civic a b

Sample Input 2

aabaa

Sample Output 2

a a b a a
a a b aa
a aba a
aa b a a
aa b aa
aabaa