Коровы играют в игру со множеством из \(N\) интервалов (\(1\le N\le 2\cdot 10^5\)),
где \(i\)-ый интервал начинается в позиции \(a_i\) на числовой прямой, а заканчивается в позиции
\(b_i \geq a_i\). Оба числа \(a_i\) and \(b_i\) - целые, в интервале \(0 \ldots M\), где
\(1 \leq M \leq 5000\).
Чтобы играть в эту игру, Беси выбирает некоторый интервал, например \(i\)-ый.
И Эльза выбирает некоторый интервал, например, \(j\)-ый, возможно тот же самый.
Для заданной величины \(k\) они выигрывают, если
\(a_i + a_j \leq k \leq b_i + b_j\).
Для всех \(k\) в интервале \(0 \ldots 2M\), посчитайте количество упорядоченных пар
\((i,j)\) для которых Беси и Эльза выиграют в эту игру.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит \(N\) и \(M\). Каждая из последующих \(N\) строк
описывает интервал в терминах целых чисел \(a_i\) и \(b_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(2M+1\) строку, по одной для каждого \(k\) в интервале \(0 \ldots 2M\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 5
1 3
2 5
|
0
0
1
3
4
4
4
3
3
1
1
|