Cắt rồi ghép xâu

Cho một chuỗi cố định độ dài $n$. Mỗi thao tác cắt đoạn ký tự từ vị trí $a$ đến $b$ khỏi vị trí hiện tại và dán nguyên đoạn đó vào cuối chuỗi. Hãy in chuỗi sau mọi thao tác.

Với thao tác $a$ $b$, lấy đúng các ký tự đang ở vị trí $a,\dots ,b$, xóa chúng khỏi xâu rồi nối nguyên thứ tự của đoạn ấy vào cuối. Mọi vị trí được đánh số từ $1$ trên trạng thái trước thao tác.

Input

• Dòng đầu chứa $n$ $m$. Dòng thứ hai chứa xâu ban đầu dài $n$. Mỗi dòng trong số $m$ dòng tiếp theo chứa $a$ $b$.

Output

• In xâu sau khi thực hiện toàn bộ thao tác.

Constraints

• $1\le n,m\le 2\cdot 10^5$.
• $1\le a\le b\le n$; độ dài xâu luôn bằng $n$.

Scoring

• Subtask small: $50$ điểm, gồm $10$ test nhỏ.
• Subtask full: $50$ điểm, gồm $10$ test không có giới hạn bổ sung ngoài phần Constraints.
• Mỗi test có giá trị $5$ điểm.

Example

7 3
ABCDEFG
2 5
3 4
1 2

CDEGBAF