|
Time |
Memory |
| Case 1 |
1 sec |
32 MB |
| Case 2 |
1 sec |
32 MB |
| Case 3 |
1 sec |
32 MB |
| Case 4 |
1 sec |
32 MB |
Description
Niflheimr is playing cards again!
One day, one of his friends, Ken, suspect that Niflheimr was cheating while shuffling cards. Fortunately, Niflheimr records all the operations he did while shuffling cards, so he wants to undo those operations step by step to find out the original card stack. As an intellegent CS student, let's write a program to help Niflheimr prove his innocence!
Input
First line of input contains two integer n, m, representing # of cards and # of operations.
Next line contains n integers, representing the number on each card from the top (index 0) to the buttom (index n-1) after doing all operations.
Each of the next m lines contains an operation. Operations are in original order.
An operation consists of two integers a and b, meaning Niflheimr moves cards whose index are between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part won't be changed.
Index of a card means # of cards on the top of that card. It may change after operations.
It is guaranteed that:
- 1 ≤ n, m ≤ 104
- Number on cards are non-negative integer and do not exceed 107
- In each operation, card with index = a+b-1 always exists.
Output
Print out the original card stack from top (index 0) to buttom (index n-1), each number occupies one line.
Tags