Xâu lặp

Xâu lặp là một xâu có đoạn đầu ngắn nhất của nó được lặp lại nhiều lần. Ví dụ ‘xyxyxyxy’ là một xâu lặp vì nó có đoạn đầu ngắn nhất là ‘xy’ được lặp lại nhiều lần. ‘xyxy’ cũng được lặp lại nhưng không được tính là đoạn đầu vì nó không ngắn nhất.

Yêu cầu: Cho $n$ xâu. Hãy ghép đoạn đầu của mỗi xâu lặp theo thứ tự xuất hiện của xâu (nếu xâu đó là xâu lặp).

Đọc từ file văn bản SUBSTR.INP gồm nhiều dòng:

• Dòng 1: Chứa số nguyên dương $n$ ($1 \le n \le 10^3$) là số lượng xâu.
• $n$ dòng tiếp theo, mỗi dòng chứa một xâu có độ dài không quá $10^3$ kí tự.

Lưu ý: Trong xâu chỉ chứa kí tự thường từ ‘a’ đến ‘z’ trong bảng chữ cái Tiếng Anh (không chứa khoảng trắng, kí tự số và các kí tự đặc biệt). Dữ liệu vào đảm bảo luôn có xâu lặp.

Ghi ra file văn bản SUBSTR.OUT là xâu ghép thu được.

• $1 \le n \le 10^3$.
• Mỗi xâu có độ dài không quá $10^3$ kí tự.