היום מתוכננים להתפרסם ב-Songjuk Haksa $N$ פרויקטים. Jongyoung וחבריו אינם רוצים לעבוד הרבה, ולכן החליטו לחלוק ביניהם את הפרויקטים ולממש אותם.

אפשר לגשת לפרויקט $i$ בזמן $L_i$, ויש להשלים את מימושו בזמן $R_i$ או לפניו, אך יכולת הלמידה של הסטודנטים אינה טובה במיוחד, ולכן העבודה על הפרויקט צורכת את כל הזמן הזמין.

בנוסף, סטודנט אינו יכול לפתור כמה פרויקטים באותו זמן. לכן, אם סטודנט בחר בשני פרויקטים $i$ ו-$j$, חייב להתקיים $R_i<L_j$ או $R_j<L_i$. כמו כן, הסטודנטים אינם מעוניינים במיוחד בעבודה קשה, ולכן כל סטודנט יעבוד על שני פרויקטים לכל היותר.

קבוצה של $M$ סטודנטים חזקים רוצה לממש יחד פרויקטים רבים ככל האפשר. עזרו להם להחליט אילו פרויקטים כל סטודנט צריך לפתור. אם יש כמה דרכים אפשריות, תוכלו לבחור כל אחת מהן.

קלט

השורה הראשונה של הקלט מכילה שני מספרים שלמים $N$ ו-$M$, מספר הפרויקטים ומספר הסטודנטים, בהתאמה ($1\le M\le N\le3\cdot10^5$).

כל אחת מ-$N$ השורות הבאות מכילה שני מספרים שלמים $L_i$ ו-$R_i$: זמני ההתחלה והסיום של הפרויקט ה-$i$ ($1\le L_i<R_i\le10^9$).

פלט

הדפיסו $N$ מספרים שלמים. המספר ה-$i$ צריך להיות מספרו של הסטודנט (מ-$1$ עד $M$) שיטפל בפרויקט $i$. אם אף סטודנט לא יבצע את הפרויקט $i$, הדפיסו במקום זאת 0.

מספר הפרויקטים שמומשו חייב להיות מרבי. אם קיימים כמה פתרונות אפשריים, הדפיסו כל אחד מהם.

דוגמאות

קלט 1

7 5
9 10
7 9
3 4
9 10
2 6
8 9
5 8

פלט 1

3 2 2 5 5 4 1

קלט 2

2 2
1 2
3 4

פלט 2

1 1

קלט 3

2 1
1 2
2 3

פלט 3

1 0