P12293 [AOJ] Distribution Center
普及
题目描述

Example

Input

4 3
1000 1
2000 2
3000 3

Output

2 3 4 4

输入格式

见题面

输出格式

见题面

样例输入
4 3 1000 1 2000 2 3000 3
样例输出
2 3 4 4