Ngày hôm nay có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko ham ăn muốn đi ăn ~q~ lượt, mỗi lượt từ gian hàng ~l~ đến gian hàng ~r~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Input

• Dòng đầu gồm 2 số ~n, q~.
• ~q~ dòng tiếp theo mỗi dòng thứ ~i~ gồm 2 số ~l_i, r_i~ ~(1 \le l_i \le r_i \le 10^5)~ là lượt đi ăn thứ ~i~.

Output

• In ra ~n~ số ứng với ~n~ cửa hàng là số lần Yuyuko vào gian hàng.

Sample Test

Input:

4 3
1 3
2 4
1 2

Output:

2 3 2 1