Background

The little square saw with its own eyes that its former friend was swept into a dark abyss, yet it was powerless to stop it……

Now its friend has attacked it, so the little square has no choice but to fight back.

Problem Description

We treat the lake on the mountaintop as a straight line of length $m$. At the beginning, the water depth everywhere is on the baseline, and we regard the water depth at this time as '0'.

Next, in an instant, the little square’s "friends" jump up and dive into the water, causing the water level at the entry point to drop and the water level far away from the entry point to rise. Note that two "friends" may enter the water at the same position.

Each friend of the little square has a volume value $v$. When a friend with volume $v$ jumps into the water, let the entry point be $i$. This will cause the water levels from $i - v + 1$ to $i$ to decrease by $1,2,\cdots,v$ respectively.

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

Correspondingly, the water level at $i - v$ does not change. The water levels from $i - v - 1$ to $i - 2 * v$ increase by $1,2,\cdots,v$ respectively, and the water levels from $i - 2 * v$ to $i - 3 * v + 1$ increase by $v,v - 1,\cdots,1$ respectively.

Similarly, the water level at $i + v$ does not change. The water levels from $i + v + 1$ to $i + 2 * v$ increase by $1,2,\cdots,v$ respectively, and the water levels from $i + 2 * v$ to $i + 3 * v - 1$ increase by $v,v - 1,\cdots,1$ respectively.

Now the little square wants to cross this lake. It wants to know the water level at each position of the lake after these $n$ "friends" have jumped into the water. Can you help it?

Input Format

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

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

Output Format

Output one line with $m$ integers. The $i$-th integer represents the water depth at position $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

Hint

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

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

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

Translated by ChatGPT 5