CSES - TCR Contest - Reversals
  • Time limit: 2.00 s
  • Memory limit: 128 MB

You are given a string of n characters. In addition you get m queries, each reversing a substring. Your task is to compute the final string.

Input

The first line consists of two integers, n and m, the length of the string and the number of reversal operations, respectively.

Next line consists of a single string with length n. The string consists of characters a-z with indices 1, 2, \ldots, n.

The rest m lines each describe a single reversal operation. Each line consists of two integers, a and b, which describe the substring to reverse (from index a to index b, inclusive).

Output

Output a single line consisting of the final string.

Constraints

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

Example

Input:

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

Output:

axowhadoqj