Sau khi học trên các lớp traning về hàm và chương trình con thì các bạn sinh viên muốn làm nhiều bài tập về chủ đề này hơn để thuần thạo khả năng code của mình.

Ở bài này, bạn nhận được một mảng có N phần tử và Q thao tác đảo ngược mảng.

Thao tác đảo ngược mảng được hiểu như sau:

Ở mỗi thao tác, bạn sẽ nhận được hai số là L và R đại diện cho đoạn mảng con từ phần tử thứ L đến phần tử thứ R. Sau đó, bạn phải thay đổi đoạn mảng con đó bằng cách đảo ngược lại để được thứ tự mới.

Ví dụ:

Đoạn mảng con đó là A[L], A[L+1], ... A[R-1], A[R] thì đoạn mảng con đó sẽ được đảo ngược lại thứ tự là: A[R], A[R-1], ...A[L+1], A[L].

Do có nhiều thao tác nên bạn phải bắt buộc đảo ngược mảng theo thứ tự lần lượt Q thao tác đấy, có nghĩa là phải đạo được đoạn L1, R1 -> L2,R2...->LQ, RQ.

Thực hiện xong bạn in ra mảng với thứ tự cuối cùng đạt được

Input

Dòng đầu tiên chứa hai số nguyên N (N ≤ ~10^5~) và Q (Q ≤ ~100~) đại diện cho số lượng phần tử mảng và Q thao tác.

Dòng thứ hai chứ N số nguyên dương (A[i] ≤ ~10^9~ ).

Q dòng tiếp theo chứa hai số nguyên Li, Ri để mô tả đoạn mảng con thứ i cần phải đảo có thứ tự từ L -> R (1 ≤ L < R ≤ N).

Output

In ra một dòng duy nhất các giá trị mảng với thứ tự được thay đổi sau cùng.

Examples

Input

5 2
1 2 3 4 5
2 4
4 5

Output

1 4 3 5 2

*Giải thích: * Thứ tự mảng sau khi đổi từ vị trí 2 đến 4 là: 1 4 3 2 5. Sau đó đổi tiếp tục từ vị trí 4 đến 5 sẽ được: 1 4 3 5 2.

Gợi ý: Có thể áp dụng chương trình con để viết với chức năng đảo thứ tự từ phần tử thứ L-> R, và mỗi lần nhập L, R thì ta gọi hàm để thực hiện.