Mạch DNA

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à: $TTTGTTACCCCТ$.

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 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 ra

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ài chuỗi $S$ không vượt quá $1000$.
• Chuỗi sau khi giải nén có độ dài không vượt quá ${10}^5$.

Ví dụ