Problem Background

Little Square has witnessed its昔日 friends being drawn into the abyss of darkness, yet it was powerless to stop them...

Now, its friends have launched an attack on it, so Little Square has no choice but to resist.

Problem Description

We consider the lake at the top of the mountain as a straight line of length $m$, where the water depth is initially at the horizontal level, which we consider as a water depth of '0'.

Next, in an instant, Little Square's "friends" jump and plunge into the water, causing the water depth at the entry point to decrease and the water depth away from the entry point to increase. Note that two "friends" may enter the water at the same location.

Each of Little Square's friends has a volume value $v$. When a friend with volume $v$ jumps into the water, we set the entry point as $i$, which will cause the water levels from $i - v + 1$ to $i$ to decrease sequentially by $1, 2, \cdots, v$.

Similarly, the water levels from $i$ to $i + v - 1$ will decrease sequentially by $v, v - 1, \cdots, 1$.

Correspondingly, the water level at $i - v$ remains unchanged, the water levels from $i - v - 1$ to $i - 2 * v$ increase sequentially by $1, 2, \cdots, v$, and the water levels from $i - 2 * v$ to $i - 3 * v + 1$ increase sequentially by $v, v - 1, \cdots, 1$.

Likewise, the water level at $i + v$ remains unchanged, the water levels from $i + v + 1$ to $i + 2 * v$ increase sequentially by $1, 2, \cdots, v$, and the water levels from $i + 2 * v$ to $i + 3 * v - 1$ increase sequentially by $v, v - 1, \cdots, 1$.

Now, Little Square wants to cross this lake and needs to know the water level at each node on the lake after these $n$ "friends" jump into the water. Can you help it?

Input Format

The first line contains two integers $n$ and $m$, representing the number of "friends" and the width of the lake, respectively.

The next $n$ lines each contain two integers $v$ and $x$, representing the volume and entry point of the $i + 1$-th friend, respectively.

Output Format

One line containing $m$ integers, where the $i$-th integer represents the water depth at the $i$-th position.

Sample Input and Output

Sample Input #1

1 10
1 5

Sample Output #1

0 0 1 0 -1 0 1 0 0 0

Sample Input #2

2 10
2 6
3 1

Sample Output #2

-2 0 0 0 0 0 2 2 2 2

Notes

For $30\%$ of the data, $n <= 50, m <= 500$.

For $70\%$ of the data, $n <= 10^5, m <= 10^5$.

For $100\%$ of the data, $n <= 10^6, m <= 10^6, 1 <= v <= 10000, 1 <= x <= m$.

见题面 Input 部分

见题面 Output 部分