F. TorCoder
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

Мальчик Лео не пропускает ни одного раунда соревнований TorCoder. На последнем TorCoder раунде под номером 100666 Лео столкнулся со следующей задачей. Задана строка s, состоящая из n строчных букв латинского алфавита, а также m запросов. Каждый запрос характеризуется парой целых чисел li, ri (1 ≤ li ≤ ri ≤ n).

Будем считать, что буквы строки пронумерованы от 1 до n слева направо, то есть s = s1s2... sn.

После каждого запроса необходимо поменять местами буквы строки s, с номерами от li до ri включительно так, чтобы подстрока (li, ri) стала палиндромом. Если существует несколько таких перестановок букв, нужно выбрать ту, в которой подстрока (li, ri) будет лексикографически наименьшей. Если не существует ни одной такой перестановки — запрос нужно проигнорировать (то есть никак не менять строку s).

Всем известно, что на раундах TorCoder ограничения на размер входных строк и массивов никогда не превышают 60, поэтому Лео с легкостью решил эту задачу. Вам же нужно решить эту задачу на несколько больших ограничениях. По заданной строке s и m запросам, выведите строку, которая получится в результате применения всех m запросов к строке s.

Входные данные

В первой строке входных данных находится два целых числа n и m (1 ≤ n, m ≤ 105) — длина строки и количество запросов.

Во второй строке находится строка s, состоящая из n строчных латинских букв.

В каждой из следующих m строк находится пара чисел li, ri (1 ≤ li ≤ ri ≤ n) — очередной запрос, который нужно применить к строке.

Выходные данные

В единственной строке выведите результат применения m запросов к строке s. Выполняйте запросы, в том порядке, в котором они заданы во входных данных.

Примеры
Входные данные
7 2
aabcbaa
1 3
5 7
Выходные данные
abacaba
Входные данные
3 2
abc
1 2
2 3
Выходные данные
abc
Примечание

Подстрокой (li, ri) 1 ≤ li ≤ ri ≤ n) строки s = s1s2... sn длины n называется последовательность символов slisli + 1...sri.

Строка называется палиндромом, если она читается одинаково слева направо и справа налево.

Строка x1x2... xp лексикографически меньше строки y1y2... yq, если либо p < q и x1 = y1, x2 = y2, ... , xp = yp, либо существует такое число r (r < p, r < q), что x1 = y1, x2 = y2, ... , xr = yr и xr + 1 < yr + 1.