Коровы играют в игру со множеством из n интервалов, где i-ый интервал начинается в позиции a[i]
на числовой прямой, а заканчивается в позиции b[i]
≥ a[i]
. Оба числа a[i]
and b[i]
- целые, в интервале 0..m, где 1 ≤ m ≤ 5000.
Чтобы играть в эту игру, Беси выбирает некоторый интервал, например i-ый. И Эльза выбирает некоторый интервал, например, j-ый, возможно тот же самый. Для заданной величины k они выигрывают, если a[i]
+ a[j]
≤ k ≤ b[i]
+ b[j]
.
Для всех k в интервале 0..2m, посчитайте количество упорядоченных пар (i, j) для которых Беси и Эльза выиграют в эту игру.
Первая строка ввода содержит n (1 ≤ n ≤ 2 * 10^5
) и m. Каждая из последующих n строк описывает интервал в терминах целых чисел a[i]
и b[i]
.
Выведите 2 * m + 1 строку, по одной для каждого k в интервале 0..2m.
В этом примере для k = 3, имеется 3 упорядоченных пары, которые позволяют Беси и Эльзе выиграть: (1, 1), (1, 2) и (2, 1).