Chính có một món đồ chơi giải đố cho trẻ em 5 tuổi, đồ chơi có thể được biểu diễn thành một xâu \(s\) gồm \(n\) kí tự latin thường. Một ngày, em họ của Chính đến nhà chơi và đã \(q\) lần nghịch đồ chơi của anh, lần thứ \(i\) em của Chính đã đổi tất cả các kí tự \(u_i\) trong xâu \(s\) thành kí tự \(v_i\). Sau khi phát hiện ra, Chính không chỉ không tức giận mà ngược lại còn rất hứng thú với trò nghịch ngợm của em họ. Chính quay sang đố bạn xác định xâu \(s\) cuối cùng sau \(q\) lần phá của em họ Chính.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, q\) (\(n, q \leq 10^5\)).
• Dòng thứ hai gồm một xâu \(s\), chỉ gồm các kí tự latin thường.
• Trong \(q\) dòng tiếp theo, dòng thứ \(i\) gồm hai kí tự \(u_i, v_i\).

Output

• In ra duy nhất một xâu là đáp án của bài toán.

Example

7 4
contest
et
ta
mo
no

cooaasa

4 3
aaaa
ba
ab
bc

cccc

Ràng buộc

• \(30\%\) số điểm có \(n, q \leq 10^3\).
• \(30\%\) số điểm tiếp theo thỏa mãn xâu \(s\) chỉ có duy nhất một loại kí tự.
• \(20\%\) số điểm tiếp theo thỏa mãn xâu \(s\) chỉ có hai loại kí tự.
• \(20\%\) số điểm còn lại có \(n, q \leq 10^5\).