- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ممد و رضا یک بازی دونفره با هم انجام میدهند. ممد \(n\) نقطه که هیچ سهتایی روی یک خط نیستند، روی صفحه میگذارد و از رضا میخواهد تعدادی از این نقطه هارا طوری بهم وصل کند که یک درخت دودویی کامل با ارتفاع \(k\) شود. تنها شرط مسأله این است که یال های درخت نباید همدیگر را قطع کنند.
درخت دودویی، درختی است که هریک از راسهای آن دقیقا دقیقا دو یاصفر فرزند دارند. درخت دودویی کامل با ارتفاع \(k\) درخت دودوییای است که تا ارتفاع \(k-1\) همه راس های آن دقیقا دو فرزند دارند و راس های ارتفاع \(k\)ام هیچ فرزندی ندارند. راس های درخت دودویی را از 1 تا \(2^k-1\) شماره گذاری میکنیم طوری که فرزندان راس \(i\)ام دو راس \(2i\) و \(2i+1\) باشند.
به رضا کمک کنید که یک نقاشی مناسب بکشد. شما باید به ازای هر نقطه بگویید چه راسی باید در آن قرار بگیرد، طوری که با کشیدن یال های درخت، یالها با هم تقاطع نداشته باشند.
ورودی
در اولین خط ورودی اعداد \(n\), \(k\) آمدهاست. که به ترتیب تعداد نقطهها و ارتفاع درخت است، داده میشود. در هرکدام از \(n\) خط بعدی، در هر سطر دو عدد صحیح \(x_i, y_i\) میآید که مختصات نقطه \(i\)ام در صفحه را نشان میدهد. تضمین میشود هیچ ۳ نقطهای روی یک خط نباشند. \[3 \le n \le 1\ 500\] \[{-10}^9 \le x_i, y_i \le 10^9\] \[1 \le 2^k-1 \le n\]
خروجی
در \(n\) سطر خروجی و در سطر \(i\)ام شماره راسی را چاپ کنید که به نقطه \(i\)ام (به ترتیبی که در ورودی داده شده است) نسبت دادهایم و اگر هم این نقطه در بین راس های درختتان نیست، عدد ۰ را برایش چاپ نمایید. اگر با نقطه های موجود نمیتوان هیچ درخت دودویی را کشید که یال هایش همدیگر را قطع نکنند، تنها در یک سطر عدد ۱- را چاپ کنید. دقت نمایید که جوابها لزوما یکتا نیستند.
مثال
ورودی نمونه
9 2
100 300
200 300
500 301
200 200
300 201
400 203
500 206
300 101
402 100
خروجی نمونه
4
1
0
2
0
3
6
5
7
نقاشی زیبای ممد برای این مثال برای فهم بهتر رضا از بازی :
