Згорнуті інтервали
Корови грають у гру з множиною з n інтервалів, де i-ий інтервал починається в позиції a[i] на числовій прямій, а закінчується в позиції b[i] ≥ a[i]. Обидва числа a[i] і 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).