Cho mạch mã gốc DNA bốn loại nucleotide A, T, G, C. Để tiết kiệm bộ nhớ, mạch mã gốc đã được nén lại thành một chuỗi ~S~ gồm các cặp là số lần xuất hiện liên tiếp nucleotide và loại nucleotide tương ứng.

Ví dụ: Mạch mã gốc AAACAATGGGGA nén thành 3A1C2A1T4G1A.

Các nucleotide ở hai mạch của phân tử DNA liên kết với nhau theo nguyên tắc bổ sung, trong đó A liên kết với T, G liên kết với C. Do vậy, nếu biết trình tự nucleotide trên một mạch có thể suy ra trình tự của mạch còn lại.

Ví dụ: Một đoạn phân tử DNA ở sinh vật nhân thực có trình tự nucleotide trên mạch mã gốc là AAACAATGGGGA. Trình tự nucleotide trên mạch bổ sung của đoạn DNA này là: TTTGTTACCCCT.

Yêu cầu

Cho một chuỗi ký tự ~S~ mô tả mạch mã gốc DNA sau khi đã nên. Hãy lập trình xác định mạch bổ sung của mạch mã gốc sau khi giải nén.

Dữ liệu đầu vào

Một chuỗi ~S~ có độ dài không vượt quá ~1000~. Dữ liệu đảm bảo chuỗi sau khi giải nén có độ dài không vượt quá ~10^5~.

Dữ liệu đầu ra

Gồm chuỗi ký tự là mạch bổ sung của mạch mã gốc sau khi giải nén.

Ràng buộc dữ liệu

• Có 20% số test ứng với 20% số điểm của bài thỏa mãn: độ dài chuỗi ~S~ là ~2~, trong đó ký tự đầu tiên là chữ số, ký tự thứ hai là một trong ~4~ chữ cái A, T, G, C;
• Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: có duy nhất một loại nucleotide;
• Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: số lần xuất hiện liên tiếp nucleotide A, T, G, C nhỏ hơn ~10~;
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5A2G1A11T1C

OUTPUT

TTTTTCCTAAAAAAAAAAAG

Giải thích: Mạch mã gốc sau khi giải nén là: AAAAAGGATTTTTTTTTTTC. Mạch bổ sung là: TTTTTCCTAAAAAAAAAAAG.