+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ممد و رضا یک بازی دونفره با هم انجام می‌دهند. ممد ‌$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 ``` نقاشی زیبای ممد برای این مثال برای فهم بهتر رضا از بازی : ****

حل سؤال در بانک سؤالات