복잡한 구간

소들이 재미있는 새 놀이를 고안하느라 바쁘다. 그중 하나는 $N$개의 구간을 사용하는 놀이로, $i$번째 구간은 수직선 위의 $a_i$에서 시작해 $b_i \geq a_i$에서 끝난다. $a_i$와 $b_i$는 모두 $0 \ldots M$ 범위의 정수이며, $1 \leq M \leq 5000$이다.

놀이를 하려면 Bessie가 어떤 구간을 고르고(예를 들어 $i$번째 구간), 사촌 Elsie가 어떤 구간을 고른다(예를 들어 $j$번째 구간, Bessie와 같은 구간이어도 된다). 어떤 값 $k$가 주어졌을 때 $a_i + a_j \leq k \leq b_i + b_j$이면 두 소가 이긴다.

$0 \ldots 2M$ 범위의 각 $k$에 대해, Bessie와 Elsie가 이길 수 있는 순서쌍 $(i,j)$의 개수를 구하라.

첫 줄에 $N$과 $M$이 주어진다. 다음 $N$개의 줄에 각 구간이 정수 $a_i$와 $b_i$로 주어진다.

$0 \ldots 2M$ 범위의 각 $k$에 대해 한 줄씩, 총 $2M+1$개의 줄을 출력하라.