Мальчик Лео не пропускает ни одного раунда соревнований 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.
Выходные данные
В единственной строке выведите результат применения m запросов к строке s. Выполняйте запросы, в том порядке, в котором они заданы во входных данных.
Примечание
Подстрокой (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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
aabcbaa
1 3
5 7
|
abacaba
|
|
2
|
3 2
abc
1 2
2 3
|
abc
|