Cho một xâu, nhiệm vụ của bạn là xử lý các thao tác trong đó bạn cắt một xâu con và dán nó vào cuối xâu. Xâu cuối cùng sau tất cả thao tác là gì?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): độ dài của xâu và số lượng thao tác. Các ký tự của chuỗi được đánh số \(1, 2,\ldots, n\).
• Dòng tiếp theo có một xâu độ dài \(n\) bao gồm các kí tự A–Z.
• Cuối cùng, có \(m\) dòng mô tả các thao tác. Mỗi dòng có hai số nguyên \(a\) và \(b\): bạn cắt một xâu con từ vị trí \(a\) đến vị trí \(b\).

Output

• In xâu cuối cùng sau tất cả thao tác.

Constraints

• \(1 \leq n, m \leq 2 \cdot 10 ^ 5\)
• \(1 \leq a \leq b \leq n\)

Example

Sample intput

7 2
AYBABTU
3 5
3 5

Sample output

AYABTUB