You are given an integers array $A$ of length $n$ and $q$ queries of form $i \\; x$, insert value $x$ at position $i$ of $A$. Print array $A$ after each query.
### Input
- The first line contains 2 integers $n, q$.
- The second line contains $n$ integers $A_i$.
- Each line in the next $q$ line contains 2 integers $i \\; x$ denotes a query. It is guaranteed that every query is valid.
### Output
- Print $q$ line, $i^{th}$ line is the array $A$ after $i^{th}$ query.
### Constraints
- $1 \le n, q \le 100$.
- $|A_i|, |x| \le 100$.
### Example
Input:
```
3 3
1 2 3
1 0
5 5
5 4
```
Output:
```
0 1 2 3
0 1 2 3 5
0 1 2 3 4 5
```