Given an array $A$ consists of $n$ zero. You are also given $q$ queries, each of the form $(l, r)$ means that for every element $A_i$ with $l \le i \le r$, increase it by $i - l + 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 all queries.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le l, r \le n$.
### Example
Input:
```
4 2
1 3
2 4
```
Output:
```
1 3 5 3
```
Note: After the first query, $A$ becomes $\\{1, 2, 3, 0\\}$.
