Bạn được cho một dãy DNA gồm các kí tự A, C, G và T.

Nhiệm vụ của bạn là tìm dãy DNA ngắn nhất mà không phải là dãy con (có thể thu được bằng cách xóa một số kí tự) của dãy gốc.

Input

• Dòng đầu vào duy nhất chứa một dãy DNA với \(n\) kí tự.

Output

• In dãy DNA ngắn nhất mà không phải là dãy con của dãy gốc. Nếu có một số giải pháp, bạn có thể in bất kì giải pháp nào trong số đó.

Constraints

• \(1 \leq n \leq 10 ^ 6\)

Example

Sample input

ACGTACGT

Sample output

AAA