Cho một xâu, nhiệm vụ của bạn là xử lý các thao tác trong đó bạn đảo ngược một xâu con của xâu. Xâu cuối cùng sau tất cả các thao tác là gì?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): độ dài của xâu và số lượng thao tác. Các ký tự của xâu được đánh số \(1, 2, \ldots, n\).
• Dòng tiếp theo có một xâu độ dài \(n\) bao gồm các ký tự A–Z.
• Cuối cùng, có \(m\) dòng mô tả các thao tác. Mỗi dòng có hai số nguyên \(a\) và \(b\): bạn đảo ngược một xâu con từ vị trí \(a\) đến vị trí \(b\).

Output

• In xâu cuối cùng sau tất cả các thao tác.

Constraints

• \(1 \leq n, m \leq 2 \cdot 10 ^ 5\)
• \(1 \leq a, b \leq n\)

Example

Sample input

7 2
AYBABTU
3 4
4 7

Sample output

AYAUTBB