Tuấn có một chuỗi ký tự chỉ gồm các chữ cái thường tiếng Anh và đang cố mã hóa chuỗi này theo một mã hóa nhất định.

Mã hóa này được mô tả bởi hai chuỗi ~A~ và ~B~, trong đó mỗi ký tự ở chuỗi ~A~ được ánh xạ tới một ký tự tương ứng trong chuỗi ~B~. Ví dụ, nếu

• ~A = ~ abcdefghijklmnopqrstuvwxyz
• ~B = ~ zyxwvutsrqponmlkjihgfedcba,

thì a sẽ được ánh xạ thành z, b sẽ thành y, ....

Việc biến đổi chuỗi chỉ một lần thì khá nhàm chán, vì vậy, với một số nguyên dương ~K~, Tuấn muốn lặp lại quá trình mã hóa này ~K~ lần. Nhưng giờ đây Tuấn đã mệt và nhờ bạn giúp đỡ. Bạn có thể giúp Tuấn để có được chuỗi cuối cùng không?

Dữ liệu vào từ tệp văn bản: MAHOAXAU.INP

• Dòng đầu tiên chứa xâu ~S \ (1 \leq |S| \leq 10^5)~ chỉ gồm các kí tự La-tinh in thường.
• Dòng tiếp theo chứa một số nguyên dương ~K \ (1 \leq K \leq 10^9)~.
• Hai dòng tiếp theo, mỗi dòng chứa lần lượt hai xâu ~A~ và ~B~ có đúng ~26~ kí tự là hoán vị của các kí tự La-tinh in thường từ a đến z.

Kết quả ghi ra tệp văn bản: MAHOAXAU.OUT

• In ra một xâu duy nhất là kết quả bài toán.

Scoring

• Subtask 1 (~30 \%~ số điểm): ~K = 1~.
• Subtask 2 (~30 \%~ số điểm): ~K, |S| \leq 2000~.
• Subtask 3 (~20 \%~ số điểm): ~K \leq 10^5~.
• Subtask 4 (~20 \%~ số điểm): Không có ràng buộc gì thêm.

Sample Input

hnoi
2
abcdefghijklmnopqrstuvwxyz
pnudzgabijkyehlrqxfmsctovw

Sample Output

nbyi

Giải thích: Các kí tự của xâu hnoi được mã hóa như sau:

• h → b → n
• n → h → b
• o → l → y
• i → i → i