הפרות משקיעות מאמצים בהמצאת משחקים חדשים ומעניינים. אחד ממיזמיהן הנוכחיים משתמש בקבוצה של $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