Người ta phát hiện thấy sinh vật trên một thiên thạch rơi xuống trái đất. Lập tức thiên thạch được đưa vào phòng thí nghiệm cách ly để nghiên cứu xem sự phát triển của sinh vật có ảnh hưởng đến cuộc sống trên trái đất hay không. Đây là một sinh vật hết sức đơn giản. DNA của nó được mô tả chỉ với một trong số ~4~ ký tự {A, C, T, G}. Tuy nhiên quá trình phát triển thì hết sức độc đáo: sau mỗi khoảng thời gian DNA được kéo dài thêm một ký tự ở bên phải hoặc bên trái chuỗi đã có. Người ta cũng xác định được ký tự mới nào sẽ xuất hiện trong chuỗi DNA ở giai đoạn phát triển tiếp theo từ lúc bắt đầu cho đến khi ngừng phát triển, tuy nhiên việc ký tự mới được gắn vào bên phải hay trái của chuỗi đã có là ngẫu nhiên. Kết quả nghiên cứu cũng cho thấy sinh vật với chuỗi DNA có thứ tự từ điển càng nhỏ bao nhiêu thì sức sống càng mạnh bấy nhiêu.

Yêu cầu:

Hãy xác định DNA của cá thể có sức sống mạnh nhất.

Dữ liệu vào

• Dòng đầu tiên chứa một ký tự trong tập {A, C, T, G} – chuỗi DNA ban đầu của sinh vật,
• Dòng thứ ~2~ chứa xâu ~E~ gồm các ký tự từ tập trên, trình tự các ký tự là trình tự xuất hiện ký tự mới trong DNA. Xâu ~E~ có độ dài không quá ~10^6~.

Dữ liệu ra

Xâu xác định DNA của cá thể có sức sống mạnh nhất.

Sample Input

C
ACTG

Sample Output

ACCTG

Nguồn: Kỹ thuật lập trình - thầy Nguyễn Thanh Tùng