Annettuna on merkkijono, jossa on $n$ merkkiä. Lisäksi annettuna on $m$ kyselyä, joissa täytyy kääntää ympäri jokin merkkijonon väli. Tehtäväsi on muodostaa lopullinen merkkijono.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: merkkijonon pituus ja kääntöjen määrä.

Sitten syötteessä on merkkijono, jossa on $n$ merkkiä. Merkkijono muodostuu merkeistä a–z, ja merkit on indeksoitu $1,2,\ldots,n$.

Lopuksi syötteessä on $m$ riviä, joista jokainen kuvaa yhden käännön. Rivillä on kaksi kokonaislukua $a$ ja $b$, jotka kuvaavat käännettävän merkkijonon välin.

Tuloste

Ohjelmasi tulee tulostaa lopullinen merkkijono.

Rajat

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

Esimerkki

Syöte:

10 5
aowqxdaohj
2 5
8 9
3 4
4 9
3 4

Tuloste:

axowhadoqj