Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. TorCoder

time limit per test

3 secondsmemory limit per test

256 megabytesinput

input.txtoutput

output.txtA 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*.

Input

The first input line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 10^{5}) — 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.

Output

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.

Examples

Input

7 2

aabcbaa

1 3

5 7

Output

abacaba

Input

3 2

abc

1 2

2 3

Output

abc

Note

A substring (*l*_{i}, *r*_{i}) 1 ≤ *l*_{i} ≤ *r*_{i} ≤ *n*) of string *s* = *s*_{1}*s*_{2}... *s*_{n} of length *n* is a sequence of characters *s*_{li}*s*_{li + 1}...*s*_{ri}.

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

String *x*_{1}*x*_{2}... *x*_{p} is lexicographically smaller than string *y*_{1}*y*_{2}... *y*_{q}, if either *p* < *q* and *x*_{1} = *y*_{1}, *x*_{2} = *y*_{2}, ... , *x*_{p} = *y*_{p}, or exists such number *r* (*r* < *p*, *r* < *q*), that *x*_{1} = *y*_{1}, *x*_{2} = *y*_{2}, ... , *x*_{r} = *y*_{r} and *x*_{r + 1} < *y*_{r + 1}.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2020 07:18:23 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|