Description

有 n 棵树，初始浇水次数都是 0。有 m 次操作，每次给区间 [l,r] 内所有树浇水 1 次。输出每棵树最终被浇水的次数。

Input Format

第一行两个整数 n 和 m。接下来 m 行，每行两个整数 l 和 r。

Output Format

一行 n 个整数，表示每棵树最终被浇水次数。

5 3
1 3
2 5
4 4

1 2 2 2 1

Hint

差分 d[l]++, d[r+1]--，最后做前缀和还原。