+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک بار دیگر سال جدید رسید و همه شاد بودند؛ همه به جز عمو اسکروچ! یکی از مهم‌ترین و کهن‌ترین رسم‌ها در هنگام عید، عیدی دادن است و عمو اسکروچ از این رسم به شدت بیزار است؛ اما مجبور است به دلیل حفظ آبرو پیش در و همسایه‌ها به برادرزاده‌ها و خواهرزاده‌هایش عیدی بدهد. مراحل عیدی دادن کمی عجیب است. آن را مرحله به مرحله برای شما شرح می‌دهیم. 1. شب قبل از عید، برادرزاده‌ها و خواهرزاده‌ها همگی در یک مکان جمع می‌شوند و مشخص می‌کنند در مجموع چقدر عمو اسکروچ را تیغ می‌زنند؛ سپس به عمو‌ اسکروچ ایمیل می‌زنند و به او می‌گویند که جمعاً از او $S$ اسکروچی (یک اسکروچی معادل با یک میلیاردم بیت کوین است) به عنوان عیدی می‌خواهند. 2. عمو اسکروچ ایمیل را می‌بیند و از ترس به خود می‌لرزد. سپس با مشاورش صحبت می‌کند و مشاورش به او پیشنهاد می‌دهد که $k$ اسکناس به ارزش $a_1, ..., a_k$ در کیف پولش بگذارد. از آن‌جایی که مشاور مرد بسیار دقیقی است دنباله را چنان انتخاب می‌کند که $\sum a_i = S$ باشد. 3. در روز عید تمام $n$ برادرزاده و خواهرزاده به صورت ناگهانی به خانه عمو اسکروچ هجوم می‌آورند و $i$ امین آن‌ها طلب $p_i$ اسکروچی می‌کند. سپس عمو کیف پولش را باز می‌کند (که در آن $k$ اسکناس است) و به هر کدام از آن‌ها تعدادی اسکناس می‌دهد، به طوریکه در نهایت هر کس دقیقا به همان‌اندازه‌ای که طلب کرده بود، اسکروچی بگیرد. سپس برادرزاده‌ها و خواهر‌زاده‌ها به صورت مسالمت‌آمیز خانه عمو اسکروچ را ترک می‌کنند و تا یک سال دیگر بر نمی‌گردند (که ایده‌‌آل ترین حالت برای عمو اسکروچ است). اما ممکن است در این میان مشاور عمو اشتباه محاسباتی کرده باشد و عمو نتواند اسکناس‌ها را بین بچه‌ها تقسیم کند. در این حالت بچه‌ها داد و هوار راه می‌اندازند و عمو پیش در و همسایه‌ها شرمنده می‌شود. **توجه کنید مشاور هنگام انتخاب اسکناس‌ها مقدار $p_i$ ها را نمی‌داند.**  مراحلی که در بالا گفته شد هر سال تکرار می‌شود. یکی از دغدغه‌های عمو این است که کیف پولش سنگین و بزرگ به نظر نرسد (در اینصورت ممکن است بقیه هم او را تیغ بزنند) برای همین به مشاورش گفته است که اسکناس‌های پیشنهادی را طوری انتخاب کند که تعداد آن‌ها (همان $k$) کمینه باشد. امسال ش.پ (که یک المپیاد کامپیوتری و از دوستان عمو اسکروچ است) برای او برنامه‌ای نوشته که به کمک آن می‌تواند تشخیص دهد مشاورش چقدر بالیاقت است. برنامه به این‌صورت است که $n$ (تعداد برادرزاده‌ها و خواهرزاده‌های عمو اسکروچ)، $S$ (جمع مقداری که بچه‌ها عیدی طلب می‌کنند) و $a_1, a_2, ..., a_k$ (دنباله اسکناس‌های پیشنهادی مشاور) را تحویل می‌گیرد و یکی از سه رشته زیر را به عنوان گزارش بر می‌گرداند: - اگر حالتی از طلب کردن عیدی‌ها وجود داشته باشد که عمو نتواند عیدی‌ها را پرداخت کند و در نتیجه پیش در و همسایه‌ها شرمنده شود، برنامه رشته `wrong` را بر می‌گرداند. - در غیر این‌صورت اگر حالتی وجود نداشت که عمو شرمنده بشود ولی $k$ کمینه نبود، برنامه رشته`valid` را بر می‌گرداند. - اگر علاوه بر شرمنده نشدن، $k$ نیز کمینه بود، برنامه `optimal` را بر می‌گرداند. از آن‌جایی که ش.پ از مشکل ضعیف بودن رنج می‌برد، برنامه‌ای که نوشته بسیار کند است. عمو اسکروچ به همین منظور بخشی از بیت‌کوین‌هایش را صرف برگزاری این مسابقه کرده و می‌خواهد کسی را پیدا کند که برنامه مشابهی برای او بنویسد تا به وسیله آن مشاورش را در $q$ سال خدمت‌اش ارزیابی کند. # ورودی در خط اول ورودی عدد $q$ نوشته شده است. که تعداد سال‌های مختلفی است که عمو اسکروچ می‌خواهد مشاورش را محک بزند. سپس داده‌های مربوط به $q$ سال گذشته به صورت زیر به شما ورودی داده می‌شوند. اعداد $n$ (تعداد بچه‌ها)، $k$ (تعداد اسکناس‌های پیشنهادی مشاور) و $S$ (جمع طلب بچه‌ها) به ترتیب و در یک خط به شما ورودی داده می‌شوند. در خط بعد دنباله $a_1,a_2,...,a_k$ داده می‌شوند که اسکناس‌های پیشنهادی مشاور است. $$1 \leq n \leq 200 $$ $$ 0 \leq a_i \leq S \leq 10^{18}$$ $$\sum a_i = S$$ $$1 \leq k \leq 100\ 000$$ تضمین می‌شود که جمع تمام $k$ ها حداکثر $100\ 000$ است. # خروجی به ازای هر کدام از $q$ پرسش، جواب مسئله که یکی از سه رشته `wrong`، `valid` یا `optimal` است را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 2 4 10 4 3 2 1 2 6 10 1 1 1 1 1 5 2 4 10 1 3 3 3 ``` ## خروجی نمونه ۱ ``` optimal valid wrong ``` در پرسش دوم، تعداد اسکناس‌ها بهینه نیست ولی همچنان هرطور که ۲ بچه عیدی بخواهند می‌تواند پاسخ‌گوی نیاز آن‌ها باشد. در پرسش سوم، اگر بچه اول ۲ اسکروچی و بچه دوم ۸ اسکروچی طلب کند، عمو شرمنده می‌شود. ## ورودی نمونه ۲ ``` 2 200 6 6 1 1 1 1 1 1 200 5 6 1 1 2 1 1 ``` ## خروجی نمونه ۲ ``` optimal wrong ``` در ۲ پرسش این مثال، تعداد بچه‌ها ۲۰۰، و جمع پول درخواستی آن‌ها ۶ است. در نتیجه تعداد زیادی از آن‌ها قرار است ۰ واحد پول در‌خواست کنند. در حالتی که ۶ نفر ۱ اسکروچی بخواهند و بقیه اسکروچی نخواهند، عمو مجبور است ۶ اسکناس با ارزش ۱ داشته باشد.

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