TorCoder
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 *l**i*,<=*r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*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 (*l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>) 1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*) of string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">*n*</sub> of length *n* is a sequence of characters *s*<sub class="lower-index">*l*<sub class="lower-index">*i*</sub></sub>*s*<sub class="lower-index">*l*<sub class="lower-index">*i* + 1</sub></sub>...*s*<sub class="lower-index">*r*<sub class="lower-index">*i*</sub></sub>.

A string is a palindrome, if it reads the same from left to right and from right to left.

String *x*<sub class="lower-index">1</sub>*x*<sub class="lower-index">2</sub>... *x*<sub class="lower-index">*p*</sub> is lexicographically smaller than string *y*<sub class="lower-index">1</sub>*y*<sub class="lower-index">2</sub>... *y*<sub class="lower-index">*q*</sub>, if either *p* &lt; *q* and *x*<sub class="lower-index">1</sub> = *y*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub> = *y*<sub class="lower-index">2</sub>, ... , *x*<sub class="lower-index">*p*</sub> = *y*<sub class="lower-index">*p*</sub>, or exists such number *r* (*r* &lt; *p*, *r* &lt; *q*), that *x*<sub class="lower-index">1</sub> = *y*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub> = *y*<sub class="lower-index">2</sub>, ... , *x*<sub class="lower-index">*r*</sub> = *y*<sub class="lower-index">*r*</sub> and *x*<sub class="lower-index">*r* + 1</sub> &lt; *y*<sub class="lower-index">*r* + 1</sub>.