Xâu lặp

Cho một xâu \(s\) chỉ gồm các chữ cái Latin thường. Người ta muốn tìm một xâu \(t\) ngắn nhất sao cho bằng cách lặp lại xâu \(t\) nhiều lần (nối liên tiếp), ta có thể thu được xâu \(s\).

Ví dụ: với $s = $ abcabcabc, ta có thể thu được từ việc lặp lại xâu $t = $ abc ba lần.

Yêu cầu: Cho xâu \(s\), hãy tìm xâu ngắn nhất \(t\) sao cho \(s\) là kết quả của việc lặp lại xâu \(t\) một số lần nguyên dương.

Input

Một dòng duy nhất chứa xâu \(s\) (\(1 \le |s| \le 100\)), gồm các ký tự từ a đến z.

Output

In ra xâu \(t\) — xâu ngắn nhất thoả yêu cầu.

Notes

• Trong ví dụ đầu tiên, $s = $ abcabcabc được tạo bởi việc lặp lại abc \(3\) lần.
• Trong ví dụ thứ hai, $s = $ aaaaaa được tạo bởi việc lặp lại a \(6\) lần.
• Trong ví dụ thứ ba, không có xâu con ngắn hơn nào khi lặp lại tạo thành \(s\), nên \(t = s\).