- 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