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