Xâu Palindrome là xâu ký tự đối xứng tức là nếu ta đọc nó từ trái sang phải cũng thu được kết quả như đọc từ phải sang trái. Một xâu ký tự bất kỳ luôn có thể biểu diễn thành ghép của các xâu palindrome (xâu chỉ gồm một ký tự được xem là xâu palindrome).

Ví dụ: Xâu ‘bobseesanna’ có thể được biểu diễn thành ghép của các xâu palindrome theo nhiều cách khác nhau, chẳng hạn:

‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’

‘bobseesanna’ = ‘bob’ + ‘s’ + ‘ee’ + ’s’ + ‘anna’

‘bobseesanna’ = ‘b’ +’o’ + ‘b’ + ‘sees’ + ‘a’ + ‘n’ + ‘n’ + ‘a’

hoặc xâu ‘ab’ có thể được biểu diễn thành ‘ab’ = ‘a’ + ‘b’.

Yêu cầu: Cho xâu ký tự S, hãy tìm cách biểu diễn xâu S thành ghép của các xâu palindrome sao cho số xâu palindrome được ghép là ít nhất.

Dữ liệu vào: Đọc từ file văn bản PALINDR.INP gồm chỉ một dòng chứa một xâu ký tự S dài không quá 255 ký tự.

Dữ liệu ra: Ghi ra file văn bản PALINDR.OUT có cấu trúc như sau:

• Dòng đầu tiên ghi số k là số xâu palindrome được ghép.
• Dòng thứ i trong số k dòng tiếp theo ghi xâu palindrome p_i (i = 1, 2, ..., k) sao cho S = p₁ + p₂ + ... + p_k.

Ví dụ: