乳牛們正在努力發明有趣的新遊戲。她們目前的一個計畫涉及一組 $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$ 描述一個區間。

輸出格式

輸出 $2M+1$ 行，分別對應範圍 $0 \ldots 2M$ 內的每個 $k$。

範例

輸入格式 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