소들은 재미있는 새로운 게임을 만들기 위해 열심히 노력하고 있다. 현재 진행하는 프로젝트 중 하나는 $N$개의 구간 ($1\le N\le 2\cdot 10^5$)을 사용한다. $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$개의 줄을 출력하라.

예제

입력 1

2 5
1 3
2 5

출력 1

0
0
1
3
4
4
4
3
3
1
1

참고

이 예제에서 $k=3$만 보면 Bessie와 Elie가 승리할 수 있는 순서쌍은 $(1, 1)$, $(1, 2)$, $(2, 1)$의 세 개이다.

서브태스크

• 테스트 케이스 1-2는 $N\le 100, M\le 100$을 만족한다.

• 테스트 케이스 3-5는 $N\le 5000$을 만족한다.

• 테스트 케이스 6-20에는 추가 제한이 없다.

출력값은 32비트 정수에 담을 수 없을 만큼 클 수 있으므로 64비트 정수 (예를 들어 C 또는 C++의 "long long" 정수)를 사용하는 것이 좋다.

문제 출제: Benjamin Qi