You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小正方形亲眼看见了自己昔日的朋友被卷进了黑暗的深渊，然而它无力阻止……

现在它的朋友已经向它发起了攻击，因此小正方形不得不抵抗。

题目描述

我们把山顶上的湖泊看作一条长度为 $m$ 的直线，一开始水深都在水平线上，我们视作此时的水深为 '0'

接下来，在一瞬间，小正方形的"朋友"们跳起并扎入水中，导致在入水点的水降低而远离入水点的水升高，注意两个 "朋友" 可能在同一地点入水。

小正方形的每个朋友有一个体积数值 $v$，当体积为 $v$ 的一个朋友跳入水中，我们设入水点为 $i$，将会导致 $i - v + 1$ 到 $i$ 的水位依次降低 $1,2,\cdots,v$

同样地，第 $i$ 到 $i + v - 1$ 的水位会依次降低 $v,v - 1,\cdots,1$.

相对应地，$i - v$ 的水位不变， $i - v - 1$ 到 $i - 2 * v$ 水位依次增加 $1,2,\cdots,v$， $i - 2 * v$ 到 $i - 3 * v + 1$ 水位依次增加 $v,v - 1,\cdots,1$

同样，$i + v$ 水位不变，$i + v + 1$ 到 $i + 2 * v$ 水位增加 $1,2,\cdots,v$，$i + 2 * v$ 到 $i + 3 * v - 1$ 水位依次增加 $v,v - 1,\cdots,1$

现在小正方形想要穿过这个湖，他想要知道在这 $n$ 个"朋友"跳入水中后湖上每个节点的水位，你能帮帮它吗？

输入格式

第一行为两个整数 $n$,$m$，表示"朋友"的数目与湖泊的宽度。

接下来 $n$ 行，一行两个整数 $v,x$，表示第 $i + 1$ 个朋友的体积与入水点。

输出格式

一行 $m$ 个整数，第 $i$ 个整数表示 $i$ 号位的水深。

1 10
1 5

0 0 1 0 -1 0 1 0 0 0 

2 10
2 6
3 1

-2 0 0 0 0 0 2 2 2 2

提示

对于 $30\%$ 的数据，$n <= 50,m <= 500$

对于 $70\%$ 的数据，$n <= 10^5,m <= 10^5$

对于 $100\%$ 的数据，$n <= 10^6,m <= 10^6,1 <= v <= 10000,1 <= x <= m$