Cho một chuỗi S (tối đa 100 ký tự) chỉ gồm các chữ cái in thường, chuỗi X được gọi là ước của chuỗi S nếu chuỗi X có độ dài ngắn nhất và khi ghép một số lần X ta được chuỗi S. Ví dụ:

• S = "abababab" thì ước của nó là X = "ab"
• S = "aaaaaa" thì ước của nó là X = "a"
• S = "abc" thì ước của nó là X = "abc"

Cho trước một chuỗi S nhập từ bàn phím, hãy tìm chuỗi X là ước của chuỗi S

Input

Một dòng duy nhất chứa chuỗi S

Output

Chuỗi X là ước của chuỗi S.

Example

Input 1

abababab

Output 1

ab

Input 2

abc

Output 2

abc