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~.

Yêu cầu: 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

• Một dòng duy nhất chứa chuỗi ~X~ là ước của chuỗi ~S~.

Examples

Input

abababab

Output

ab

Input

ababc

Output

ababc

Note

Ở ví dụ 1, ta ghép 4 lần chuỗi ab được chuỗi ~S~.

Ở ví dụ 2, ta ghép 1 lần chuỗi ababc được chuỗi ~S~.