تعمل الأبقار بجد لابتكار ألعاب جديدة ممتعة. يتضمن أحد مشاريعها الحالية مجموعة من $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$.

لكل قيمة $k$ في النطاق $0 \ldots 2M$، احسب عدد الأزواج المرتبة $(i,j)$ التي تمكن Bessie وElsie من الفوز.

الإدخال

يحتوي السطر الأول على $N$ و$M$. يصف كل من الأسطر $N$ التالية مجالًا بواسطة العددين الصحيحين $a_i$ و$b_i$.

الإخراج

اطبع $2M+1$ سطرًا، سطرًا لكل قيمة $k$ في النطاق $0 \ldots 2M$.

أمثلة

الإدخال 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 بت (مثل أعداد "long long" الصحيحة في C أو C++).

مؤلف المسألة: Benjamin Qi