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