题目背景

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

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

题目描述

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

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

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

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

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

同样，$i + v$ 水位不变，$i + v + 1$ 到 $i + 2 \times v$ 水位增加 $1,2,⋯,v，i + 2 \times v$ 到 $i + 3 \times v - 1$ 水位依次增加 $v,v−1,...,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

数据范围

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

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

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