Nhà nghiên cứu sinh học, Zero đã bắt tay vào công việc nghiên cứu GEN thuần chủng.

GEN là một đoạn kết gắn các cặp ADN, mỗi cặp ADN được đặc trưng bằng một chữ cái trong tập \({A, T, X, G}\). GEN thuần chủng là là GEN hình thành từ một đoạn ADN cơ sở, được gắn kết lặp đi lặp lại nhiều lần và ở lần lặp cuối cùng có thể chỉ chứa phấn đầu của đoạn cơ sở. GEN được mô tả dưới dạng xâu \(S\) chỉ chứa các ký tự trong tập nêu trên. Như vậy GEN thuần chủng là xâu có thể biểu diễn như tổng của \(k\) đoạn cơ sở (\(k \leq 0)\) và có thể có thêm một đoạn đầu của cơ sở.

Ví dụ với \(S\) = AXATAGAXATAGAXATAGAXA là một GEN thuần chủng vì có đoạn cơ sở là AXATAG và \(S\) = AXATAG + AXATAG + AXATAG + AXA. Cho GEN \(S\) độ dài \(n\). Đưa ra đoạn cơ sở ngắn nhất của xâu \(S\).

Input

• Gồm một dòng duy nhất chứa xâu \(S\) chỉ chứa các ký tự in hoa \({A, T, X, G}\)

Output

• Gồm đoạn cơ sở ngắn nhất của xâu \(S\).

Constraints

• \(S.size() \leq 5.10^{6}\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(S.size() \leq 5.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

AXATAGAXATAGAXATAGAXA 

AXATAG