input input.txt output output.txt A boy named Leo doesn't miss a single TorCoder contest round. On the last TorCoder round number 100666 Leo stumbled over the following problem. He was given a string s , consisting of n lowercase English letters, and m queries. Each query is characterised by a pair of integers l i , r i (1 ≤ l i ≤ r i ≤ n). We'll consider the letters in the string numbered from 1 to n from left to right, that is, s = s 1 s 2... s n . After each query he must swap letters with indexes from l i to r i inclusive in string s so as to make substring (l i , r i ) a palindrome. If there are multiple such letter permutations, you should choose the one where string (l i , r i ) will be lexicographically minimum. If no such permutation exists, you should ignore the query (that is, not change string s ). Everybody knows that on TorCoder rounds input line and array size limits never exceed 60, so Leo solved this problem easily. Your task is to solve the problem on a little bit larger limits. Given string s and m queries, print the string that results after applying all m queries to string s .

输入描述:

The first input line contains two integers n and m(1 ≤ n, m ≤ 105) — the string length and the number of the queries.The second line contains string s, consisting of n lowercase Latin letters.Each of the next m lines contains a pair of integers li, ri (1 ≤ li ≤ ri ≤ n) — a query to apply to the string.

输出描述:

In a single line print the result of applying m queries to string s. Print the queries in the order in which they are given in the input.

备注:

A substring(li, ri)1 ≤ li ≤ ri ≤ n) of string s = s1s2... sn of length n is a sequence of characters slisli + 1...sri.A string is a palindrome, if it reads the same from left to right and from right to left.String x1x2... xp is lexicographically smaller than string y1y2... yq, if either p q and x1 = y1, x2 = y2, ... , xp = yp, or exists such number r(r p, r q), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 yr + 1.