nqson có 1 bộ bài gồm n lá bài với từng lá bài của bộ bài đó dược đánh 1 con số (lá bên trái cùng là lá nằm dưới đáy bộ bài). nqson sẽ tráo bộ bài q lần. Mỗi lần nqson sẽ lấy 1 tập bài từ lá thứ l đến lá thứ r (tính từ dưới đáy bộ bài, lá đầu tiên là lá thứ 1) và bỏ lên đầu của bộ bài

Hãy cho biết thứ tự các lá bài trong bộ bài của nqson sau q lần tráo.

Ví dụ: nqson có 10 lá 1, 2, 3, 4, 5, 6, 7, 8, 9, 8 (có 2 lá số 8 nha). nqson muốn tráo bài bốn lần như sau:

• Lần 1: nqson bốc từ lá thứ 2 đến lá thứ 5 lên đỉnh bộ bài, bộ bài trở thành 1, 6, 7, 8, 9, 8, 2, 3, 4, 5
• Lần 2: nqson bốc từ lá thứ 1 đến lá thứ 9 lên đỉnh bộ bài, bộ bài trở thành 5, 1, 6, 7, 8, 9, 8, 2, 3, 4
• Lần 3: nqson bốc từ lá thứ 3 đến lá thứ 7 lên đỉnh bộ bài, bộ bài trở thành 5, 1, 2, 3, 4, 6, 7, 8, 9, 8
• Lần 4: nqson bốc từ lá thứ 5 đến lá thứ 5 lên đỉnh bộ bài, bộ bài trở thành 5, 1, 2, 3, 6, 7, 8, 9, 8, 4

Kết quả cuối cùng bộ bài trở thảnh 5, 1, 2, 3, 6, 7, 8, 9, 8, 4.

Đầu vào

Dòng đầu tiên chứa hai số tự nhiên \(n\) và \(q\).

Dòng tiếp theo chứa \(n\) số tự nhiên \(a_1,a_2,a_3,...,a_n\) là số ghi trên các lá bài.

\(q\) dòng tiếp theo, mỗi dòng chứa 2 số tự nhiên \(l\) và \(r\) là vị trí của lá được bốc lên đỉnh bộ bài.

Đầu ra

In ra dãy số \(x_1,x_2,x_3,...,x_n\) là thứ tự các lá bài nqson bỏ ra

Giới hạn

\(1 \le n,q \le 10^5\)

\(1 \le a_i \le 10^{9}\)

\(1 \le x \le y \le n\)

Ví dụ

Đầu vào:

10 4
1 2 3 4 5 6 7 8 9 8
2 5
1 9
3 7
5 5

Đầu ra:

5 1 2 3 6 7 8 9 8 4