Xâu hạt nhân

Xâu $P$ được gọi là xâu hạt nhân của xâu $S$ nếu $P$ là xâu ngắn nhất mà khi ghép xâu $P$ một số lần thì được xâu $S$ (có thể chỉ cần ghép 1 lần).

Yêu cầu: Cho xâu $S$ có độ dài $k$. Hãy tìm xâu hạt nhân $P$.

Trong tệp xauhn.inp chứa xâu $S$.

Trong tệp xauhn.out ghi xâu $P$ tìm được.

Giới hạn dữ liệu: $1 \le k \le 10^5$.

Trong bộ test có:

• 60% test với $k < 255$;