你有 $k$ 台传真机。在一天中，有 $n$ 个任务依次到达，每个任务都需要花费一定的时间。对于每个任务，如果当时有空闲的传真机，它就会在其中一台机器上运行；否则，如果当时没有空闲的机器，该任务就必须被取消。作为一个容易后悔的人，你想知道如果在每个时间点都做出了最优决策，你本来可以做得有多好。与其仅仅取消任何新来的任务，你更想知道，如果你有能力中止（强行停止）一个已经在运行的任务，你还能多完成多少个任务。对于每个 $i$，输出在仅考虑前 $i$ 个任务时，使用这种更好的决策方式所能完成的最大任务数量，与实际运行的任务数量之间的非负差值。

机器在它正在运行的任务结束的瞬间立即变为空闲。

输入格式

第一行包含两个空格分隔的整数 $n, k$ ($1 \le n, k \le 2 \cdot 10^5$)。

接下来的 $n$ 行表示任务到达的顺序，其中第 $i$ 行包含两个空格分隔的整数 $t_i, l_i$：表示任务 $i$ 必须开始的时间 $t_i$，以及它需要持续的时间 $l_i$（使用相同的时间单位）。这些值满足 $0 \le t_i \le 2 \cdot 10^7$ 且 $1 \le l_i \le 2 \cdot 10^7$。

保证 $t_{i+1} \ge t_i$。

输出格式

输出 $n$ 行，其中第 $i$ 行包含在仅考虑前 $i$ 个任务时，能够完成的最大任务数量与实际运行的任务数量之间的非负差值。

样例

输入样例 1

5 1
1 3
1 1
2 1
3 1
4 2

输出样例 1

0
0
1
2
2

输入样例 2

5 2
1 3
1 1
2 1
3 1
4 2

输出样例 2

0
0
0
0
0