Given an array $A$ consists of $n$ zero. You are also given $q$ queries, each of the form $(l, r)$ which means to increment $A_l, A_{l + 1}, ..., A_r$ by 1.
### Input
- The first line contains 2 integers $n, q$.
- Next $q$ lines, each line contains 2 integers $l, r$.
### Output
- Print array $A$ after $q$ queries.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le l, r \le n$.
### Example
Input:
```
4 3
1 3
2 4
1 2
```
Output:
```
2 3 2 1
```
