Cho một xâu kí tự S gồm các chữ cái in hoa và một số nguyên dương Q tương ứng với số lượng truy vấn. Mỗi truy vấn có dạng u, v (u, v là kí tự in hoa) thay thế tất cả các kí tự u trong S thành v.

Yêu cầu: Xâu S sau Q truy vấn

Dữ liệu: Từ tệp văn bản REPLACES.INP gồm:

• Dòng đầu tiên gồm xâu S ~(|S| ≤ 10^5)~ và số nguyên dương Q

• Q dòng tiếp theo mỗi dòng gồm 2 kí tự u và v.

Kết quả : Ghi ra tệp văn bản REPLACES.OUT

• Một dòng duy nhất là xâu S sau Q truy vấn

Ví dụ:

REPLACES.INP

ABABAC 4
C D
A C
B C
C B

REPLACES.OUT

BBBBBD

Ràng buộc:

Subtask 1: (40% số điểm) có |S|, Q≤5000

Subtask 2: (60% số điểm) có |S|, ~Q≤10^5~