Sinulle on annettu merkkijono ja tehtäväsi on toteuttaa joukko operaatioita, joissa käännät ympäri jonkin merkkijonon osajonon. Millainen merkkijono on kaikkien operaatioiden jälkeen?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: merkkijonon pituus ja operaatioiden määrä. Merkkijonon merkit on numeroitu $1,2,\dots,n$.

Seuraavalla rivillä on $n$-pituinen merkkijono, joka muodostuu merkeistä A–Z.

Lopuksi syötteessä on $m$ riviä, jotka kuvaavat operaatiot. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: käännät osajonon kohdasta $a \dots b$.

Tuloste

Tulosta lopullinen merkkijono kaikkien operaatioiden jälkeen.

Rajat

• $1 \le n, m \le 2 \cdot 10^5$
• $1 \le a \le b \le n$

Esimerkki

Syöte:

7 2
AYBABTU
3 4
4 7

Tuloste:

AYAUTBB