문제
소들은 재미있는 새로운 게임을 만들려고 노력하고 있습니다. 그들의 현재 작업 중 하나는 일련의 N 간격(1≤N≤2⋅105)에 관한 것입니다. 여기서 i번째 간격은 숫자 라인의 위치 ai에서 시작하여 위치 bi≥ai에서 끝납니다. ai 및 bi는 0…M 범위의 정수이며, 여기서 1≤M≤5000입니다.
게임이 작동하는 방식은 Bessie가 간격(i번째 간격이라고 하자)을 선택하고 그녀의 사촌 Elsie가 간격을 선택하는 것입니다(j번째 간격이라고 하자. Bessie가 선택한 것과 동일한 간격일 수 있음). 어떤 값 k가 주어지면 ai+aj≤k≤bi+bj이면 승리합니다.
0…2M 범위의 각 k 값에 대해 Bessie와 Elsie가 게임에서 승리할 수 있도록 하는 순서쌍(i,j)의 수를 계산합니다.
입력
입력의 첫 번째 줄에는 N과 M이 포함됩니다. 다음 N 라인은 각각 정수 ai 및 bi의 형태로 간격을 설명합니다.
출력
0…2M 범위의 각 k에 대한 답을 차례로 포함하는 2M+1 라인을 출력합니다.
예제1
입력
2 5
1 3
2 5
출력
0
0
1
3
4
4
4
3
3
1
1
힌트
출처
USACO 2021 December Silver