Interval Pair Sum Game

Cows have devised an interesting game based on a set of \(N\) intervals. The \(i\)th interval starts at position \(a_i\) and ends at position \(b_i\) on the number line, where \(0 \leq a_i \leq b_i \leq M\) and \(1 \leq M \leq 5000\) with \(1 \leq N \leq 2\cdot10^5\).

The game is played as follows: Bessie chooses an interval \(i\) and her cousin Elsie chooses an interval \(j\) (which can be the same as \(i\)). Given a value \(k\), they win if \[ a_i + a_j \le k \le b_i + b_j. \]

Your task is: for every integer \(k\) in the range \(0\) to \(2M\) (inclusive), compute the number of ordered pairs \((i,j)\) such that the above condition holds.

inputFormat

The first line contains two integers \(N\) and \(M\). \(N\) is the number of intervals, and \(M\) is the maximum possible coordinate.

Each of the following \(N\) lines contains two non-negative integers \(a_i\) and \(b_i\) (with \(0 \leq a_i \leq b_i \leq M\)), representing an interval.

outputFormat

Output \(2M+1\) space‐separated integers. The \(k\)th number (starting from \(k=0\)) should be the number of ordered pairs \((i,j)\) such that \(a_i+a_j \le k \le b_i+b_j\).

sample

2 5
0 5
3 5

1 1 1 3 3 3 4 4 4 4 4