Для заданого рядка ваше завдання полягає в тому, щоб обробити операції, де ви змінюєте підрядок рядка на обернений.

Який кінцевий рядок після всіх операцій?

Обмеження

• \(1≤n,m≤2⋅10^5\)
• \(1≤a≤b≤n\)

Формат вхідних даних

У першому рядку вхідних даних є два цілих числа \(n\) і \(m\): довжина рядка та кількість операцій. Символи рядка пронумеровані \(1,2,…,n\).

Наступний рядок містить рядок довжиною \(n\), який складається з символів A–Z.

Далі ідуть \(m\) рядків, які описують операції. Кожен рядок містить два цілих числа \(a\) і \(b\): ви змінюєте підрядок з позиції \(a\) до позиції \(b\) на обернений.

Формат вихідних даних

Вивести останній рядок після всіх операцій.

Приклад вхідних даних

7 2
AYBABTU
3 4
4 7

Приклад вихідних даних

AYAUTBB