Згорнуті інтервали#11224
Корови грають у гру з множиною з інтервалів, де -ий інтервал починається в позиції a_i на числовій прямій, а закінчується в позиції b_i \geq a_i. Обидва числа a_i і b_i є цілими і знаходяться в межах від до , де 1 \leq m \leq 5000.
У цій грі Бессі обирає певний інтервал, наприклад, -ий. Ельза також обирає інтервал, наприклад, -ий, можливо, той самий. Для заданого значення вони виграють, якщо виконується умова a_i + a_j \leq k \leq b_i + b_j.
Для всіх в інтервалі від до , порахуйте кількість упорядкованих пар , для яких Бессі і Ельза виграють у цю гру.
Перший рядок введення містить (1 \leq n \leq 2 \cdot 10^5) і . Кожен з наступних рядків описує інтервал у вигляді цілих чисел a_i і b_i.
Виведіть 2m + 1 рядок, по одному для кожного в інтервалі від до .
У цьому прикладі для k = 3 існує упорядковані пари, які дозволяють Бессі і Ельзі виграти: , і .
Приклад 1