یکی از دانش‌پژوهان ورزشکار المپیاد کامپیوتر، بعد از زدن سرویس پرشی در بازی والیبال مصدوم شده و خانم دکتر برای مداوای او به باشگاه آمده‌است. خانم دکتر بعد از مداوای او متوجه صف بلندی از دانش‌پژوهان المپیاد کامپیوتر روبروی در سایت می‌شود، یک صف بسیار بلند که برای اعلام نتیجه‌ی آزمون عملی دوم تشکیل شده‌است. به دلایل نامعلوم (احتمالن قوی بودن تست‌کیس‌ها) مدت زیادی است که بچه‌ها منتظرند و نتیجه‌ای اعلام نشده‌است. برای همین بچه‌ها خودشان سعی دارند رتبه‌ای حدودی برای خود تخمین بزنند.

روش آن‌ها به این صورت است که $k$ نفر اول صف بر اساس عملکردی که در آزمون داشته‌اند هر کدام تخمینی اولیه از رتبه‌ی خود می‌زنند و بقیه‌ی افراد صف با توجه به رتبه‌ی افراد جلوی خود، یک رتبه تخمینی برای خود در نظر می‌گیرند. آن‌ها به ترتیب (ابتدا فرد $k + 1$ام ، سپس $k + 2$ام و …)‌ به این صورت رتبه‌ی خود را تخمین می‌زنند که رتبه‌ی $k$ نفر جلوی خود را می‌پرسند (یعنی فرد $i$ام صف از افراد $i − k$ام تا $i − 1$ام صف رتبه‌‌ی تخمینی‌شان را می‌پرسد) و با توجه به این که خیلی خوش‌بین هستند، کوچکترین رتبه‌ای را که هیچ‌ یک از $k$ نفر جلویی برای خود در نظر نگرفته را به عنوان رتبه‌ی خود در نظر می‌گیرند.

تصویر زیر تخمین شش نفر اول را در صورتی که $k = 4$ باشد نشان می‌دهد.

• در سطر اول ورودی به ترتیب دوعدد طبیعی $k$ و $n$ آمده است.
• سطر دوم دنباله‌ی $a_1, a_2, \cdots , a_k$ را نشان می‌دهد که در آن $a_i$ تخمین اولیه فرد $i$ام صف است.
• ممکن است در بین $k$ نفر اول دو نفر رتبه‌ی یکسانی تخمین زده باشند.
• $1 \leq k \leq 10^6$
• $k < n \leq 10^{12}$
• $1 \leq a_1, a_2, \cdots , a_k \leq 10^9$

در تنها سطر خروجی تخمینی که فرد $n‌$ام صف از رتبه‌ی خود دارد را چاپ کنید.

• زیرمسئله اول (۱۰ نمره): $k \leq 500$ و $n \leq 5000$
• زیرمسئله دوم (۲۰ نمره): $k \leq 500$
• زیرمسئله سوم (۴۰ نمره): $n, k \leq 10^5$
• زیرمسئله چهارم (۲۰ نمره): $k \leq 10^5$
• زیرمسئله پنجم (۱۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل