Cho xâu kí tự ~St~ có ~N~ kí tự được lấy từ tập các ký tự '~a~'...'~z~', '~A~'...'~Z~', '~0~'...'~9~' ~(0 < N\leq 255)~. Phép biến đổi xâu ~(p, q)~ ~(1\leq p, q\leq N)~ được thực hiện bằng cách hoán đổi ký tự ở vị trí ~p~ với ký tự ở vị trí ~q~ trong xâu ~St~. Ví dụ: cho Xâu ~St =~ "~abcdefgh~" và phép biến đổi xâu ~(3, 5)~ thì ta có xâu ~St~ mới là: "~abedcfgh~". Thực hiện lần lượt K phép biến đổi xâu ~(p1, q1), (p2, q2), ..., (pk, qk)~ trên xâu ~St~ thì sẽ thu được một xâu mới ~(1\leq K\leq 50)~.

Yêu cầu: Hãy tìm xâu ~St~ sau khi thực hiện lần lượt ~K~ phép biến đổi xâu.

Input

Vào từ file văn bản BDXAU.INP:

• Dòng đầu tiên gồm xâu kí tự ~St~.
• Dòng thứ hai gồm một số nguyên dương ~K~.
• ~K~ dòng tiếp theo, mỗi dòng gồm một cặp số ~p, q~.

Output

Ghi ra file văn bản BDXAU.OUT: Gồm một xâu kí tự là xâu ~St~ sau khi thực hiện ~K~ phép biến đổi.

Example input 1

abcdefgh
3
3 5
4 1
3 6

Example output 1

dbfacegh