Chuẩn bị cho đêm hội chào tân sinh viên, Liên chi đoàn Trường Công nghệ Thông tin và Truyền thông ghép một khẩu hiệu từ các tấm bìa, mỗi tấm in một chữ cái tiếng Anh in thường; xếp các tấm bìa thành một hàng ngang ta được xâu ký tự ~s~. Khẩu hiệu được treo giữa sân, khán giả đứng ở cả hai phía đều nhìn thấy, nên ban tổ chức muốn ~s~ là một xâu đối xứng – xâu mà đọc từ trái sang phải và đọc từ phải sang trái đều cho cùng một kết quả (ví dụ level, abba, a).

Trong một thao tác, ban tổ chức chọn một vị trí của khẩu hiệu và thay tấm bìa ở vị trí đó bằng một tấm bìa in chữ cái thường khác. Độ dài của xâu không thay đổi.

Yêu cầu

Gọi ~k~ là số thao tác ít nhất cần thực hiện để biến ~s~ thành một xâu đối xứng. Hãy tìm ~k~ và, trong tất cả các xâu đối xứng có thể nhận được từ ~s~ sau đúng ~k~ thao tác, tìm xâu nhỏ nhất theo thứ tự từ điển.

(Với hai xâu khác nhau có cùng độ dài, xâu ~x~ nhỏ hơn xâu ~y~ theo thứ tự từ điển nếu tại vị trí đầu tiên mà hai xâu khác nhau, ký tự của ~x~ đứng trước ký tự của ~y~ trong bảng chữ cái.)

Dữ liệu vào

Một dòng duy nhất chứa xâu ~s~ chỉ gồm các chữ cái tiếng Anh in thường (từ a đến z), không có dấu cách.

Kết quả ra

Dòng thứ nhất ghi số nguyên ~k~; dòng thứ hai ghi xâu đối xứng tìm được.

Ràng buộc

Độ dài của xâu ~s~ từ ~1~ đến ~10^5~.

• Subtask 1 (20% số điểm – test 01–04): xâu đã cho là xâu đối xứng;
• Subtask 2 (30% số điểm – test 05–10): độ dài xâu không quá ~1000~;
• Subtask 3 (50% số điểm – test 11–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

haui

Kết quả ra mẫu 1

2
haah

Dữ liệu vào mẫu 2

olympic

Kết quả ra mẫu 2

3
cipmpic

Giải thích

Ví dụ 1: hai cặp vị trí đối xứng (h, i) và (a, u) đều gồm hai ký tự khác nhau nên ~k = 2~. Sau đúng ~2~ thao tác có thể nhận được bốn xâu đối xứng haah, huuh, iaai, iuui; nhỏ nhất theo thứ tự từ điển là haah. Ví dụ 2: ba cặp (o, c), (l, i), (y, p) đều khác nhau nên ~k = 3~; ký tự chính giữa m được giữ nguyên.