b. rebranding
the name of one small but proud corporation consists of n lowercase english letters. the corporation has decided to try rebranding — an active marketing strategy, that includes a set of measures to change either the brand (both for the company and the goods it produces) or its components: the name, the logo, the slogan. they decided to start with the name.
for this purpose the corporation has consecutively hired m designers. once a company hires the i-th designer, he immediately contributes to the creation of a new corporation name as follows: he takes the newest version of the name and replaces all the letters xiby yi, and all the letters yi by xi. this results in the new version. it is possible that some of these letters do no occur in the string. it may also happen that xi coincides with yi. the version of the name received after the work of the last designer becomes the new name of the corporation.
manager arkady has recently got a job in this company, but is already soaked in the spirit of teamwork and is very worried about the success of the rebranding. naturally, he can't wait to find out what is the new name the corporation will receive.
satisfy arkady's curiosity and tell him the final version of the name.
input
the first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the length of the initial name and the number of designers hired, respectively.
the second line consists of n lowercase english letters and represents the original name of the corporation.
next m lines contain the descriptions of the designers' actions: the i-th of them contains two space-separated lowercase english letters xiand yi.
output
print the new name of the corporation.
sample test(s)
note
in the second sample the name of the corporation consecutively changes as follows:
一道想法題目：無非就是字元 x 最後映射成了另一個字元 y，操作的也就是a,b,c,d...z這26個字元。初始化ch[i]存放的是第i個字元， pos[i]=i，記錄第i個字元的位置。那麼 a<->b互換，也就是在ch[]中交換a，b兩個字元的位置(通過pos[a-'a'] 和 pos[b-'a']找到)，并同時交換pos[]的值。最終ch[i]表示字元i+'a'映射的字元。
c. median smoothing
a schoolboy named vasya loves reading books on programming and mathematics. he has recently read an encyclopedia article that described the method of median smoothing (or median filter) and its many applications in science and engineering. vasya liked the idea of the method very much, and he decided to try it in practice.
applying the simplest variant of median smoothing to the sequence of numbers a1, a2, ..., an will result a new sequence b1, b2, ..., bnobtained by the following algorithm:
b1 = a1, bn = an, that is, the first and the last number of the new sequence match the corresponding numbers of the original sequence.
for i = 2, ..., n - 1 value bi is equal to the median of three values ai - 1, ai and ai + 1.
the median of a set of three numbers is the number that goes on the second place, when these three numbers are written in the non-decreasing order. for example, the median of the set 5, 1, 2 is number 2, and the median of set 1, 0, 1 is equal to 1.
in order to make the task easier, vasya decided to apply the method to sequences consisting of zeros and ones only.
having made the procedure once, vasya looked at the resulting sequence and thought: what if i apply the algorithm to it once again, and then apply it to the next result, and so on? vasya tried a couple of examples and found out that after some number of median smoothing algorithm applications the sequence can stop changing. we say that the sequence is stable, if it does not change when the median smoothing is applied to it.
now vasya wonders, whether the sequence always eventually becomes stable. he asks you to write a program that, given a sequence of zeros and ones, will determine whether it ever becomes stable. moreover, if it ever becomes stable, then you should determine what will it look like and how many times one needs to apply the median smoothing algorithm to initial sequence in order to obtain a stable one.
the first input line of the input contains a single integer n (3 ≤ n ≤ 500 000) — the length of the initial sequence.
the next line contains n integers a1, a2, ..., an (ai = 0 or ai = 1), giving the initial sequence itself.
if the sequence will never become stable, print a single number - 1.
otherwise, first print a single integer — the minimum number of times one needs to apply the median smoothing algorithm to the initial sequence before it becomes is stable. in the second line print n numbers separated by a space — the resulting sequence itself.
in the second sample the stabilization occurs in two steps:
, and the sequence 00000 is obviously stable.
構造題目：如果a[i]==a[i+1]那麼a[i]和a[i+1]都是stable的數字，通過stable的數字将原串分成多個串si，形如0101(或1010), 01010(10101) 。
原串最終成為stable的次數，也就是子串si成為stable變換次數的最大值。那麼如何計算子串si成為stable的次數呢？其實找一下規律就好了！
0101.....10,這樣的序列,區間為[l, r], a[l]==a[r]最終變成穩定序列 0000...00。變換的次數為(r-l+1)/2;
0101.....01,這樣的序列，區間[l, r], a[l]!=a[r]最終變成穩定序列0000.....1111。0和1各占一半。變換的次數為(r-l+1)/2 -1。