Mehmet، الذي يحب ألعاب الحاسوب، يلعب «الجندب الخالد» منذ 10 ساعات. «الجندب الخالد» لعبة حاسوب تتحكم فيها بالأزرار في شخصيتك، وهي جندب يتقن الكاراتيه. والخصم الذي تواجهه هو نملة يتحكم فيها الحاسوب.

يستطيع الجندب تنفيذ $S$ هجمات مختلفة إجمالًا، حيث $1\le S\le4$. تُسمّى هذه الهجمات المختلفة بأول $S$ أحرف من الأبجدية. على سبيل المثال:

• عندما يكون $S=2$، تُسمّى الهجمات $A,B$.
• عندما يكون $S=4$، تُسمّى الهجمات $A,B,C,D$.

كل هجمة تصيب الخصم تُلحق به نقطة ضرر واحدة.

مع أنك تعرف قواعد اللعبة، فإن Mehmet نام بعد اللعب لمدة 10 ساعات، فلا يوجد من يعلمك كيفية التحكم. وجدت على الطاولة جهاز تحكم يحتوي على $N$ أزرار (مرقمة من $0$ إلى $N-1$). بعد اللعب قليلًا، أدركت أن كل زر يمكنه تنفيذ إحدى الهجمات المختلفة وعددها $S$، لكنك لا تعرف وظيفة كل زر. لحسن الحظ، ترى بفضل الملصق على أول زر أنه ينفذ هجمة من النوع $A$. كذلك تعرف أن كل نوع مختلف من الهجمات مخصص لزر واحد على الأقل.

مهمتك هي تحديد نوع الهجمة التي ينفذها كل زر على جهاز التحكم، من خلال لعب هذه اللعبة.

تلعب اللعبة على النحو الموضح أدناه. لمهاجمة النملة الخصم، تستخدم تسلسلات ضغط أزرار تسمّى مجموعات هجمات. تعمل مجموعة الهجمات كما يلي:

• تُنشئ مجموعة هجمات بالضغط على أي عدد من الأزرار بالتتابع.
• يمكنك الضغط على الأزرار بأي ترتيب داخل المجموعة.
• يمكن الضغط على الزر نفسه عدة مرات داخل المجموعة.
• أقصى طول لمجموعة الهجمات هو $400$.

تستقبل اللعبة حركاتك ثم تعرض لك إجمالي الضرر الذي ألحقته.

يُحسب مقدار الضرر الذي تُلحقه مجموعة هجمات بالنملة كما يلي. ليكن $t(X)$ الهجمة التي تلي الهجمة $X$ مباشرة في الترتيب الأبجدي. وبالنسبة إلى الهجمة الممثلة بالحرف الأخير، تُعرّف قيمة $t(X)$ بأنها الهجمة $A$. على سبيل المثال:

• عندما يكون $S=4$: $t(A)=B,t(B)=C,t(C)=D,t(D)=A$.
• عندما يكون $S=2$: $t(A)=B,t(B)=A$.

تستطيع النملة الخصم صد بعض هجماتك باستخدام أساليب ماكرة. بصورة أدق، إذا استخدمت الهجمة $X$ بوصفها آخر هجمة ناجحة (غير مصدودة) ألحقت ضررًا، ثم استخدمت الهجمة $t(X)$ بوصفها هجمتك التالية، فستصد النملة هجمتك $t(X)$ ولن تُلحق أي ضرر. وإذا لم تستطع صدها، فستُلحق بالنملة نقطة ضرر واحدة (الهجمة الأولى تُلحق ضررًا دائمًا).

هدفك معرفة الهجمات التي تنفذها جميع الأزرار والإبلاغ عنها باستخدام أقل عدد إجمالي من مجموعات الهجمات.

تفاصيل التنفيذ

يُطلب منك تنفيذ الدالة التالية:

std::string olumsuz_cekirge(int N, int S)

• تمثل القيمة $N$ عدد الأزرار على جهاز التحكم.
• تمثل القيمة $S$ عدد أنواع الهجمات المختلفة في اللعبة.
• يجب أن تعيد هذه الدالة سلسلة طولها $N$ تمثل الهجمات المخصصة للأزرار.

أثناء ذلك، يمكنك استخدام الدالة kombo التالية:

int kombo(std::vector<int> buton)

• يمكنك استدعاء الدالة kombo بحد أقصى $400$ مرة خلال كل استدعاء للدالة olumsuz_cekirge.
• تحدد المصفوفة buton فهارس الأزرار التي تريد استخدامها في مجموعة الهجمات.
• يجب أن تكون قيم المصفوفة buton أعدادًا صحيحة من $0$ إلى $N-1$.
• يمكن أن يكون طول المصفوفة buton بحد أقصى $400$.

يُطلب منك حل $T$ سيناريوهات مستقلة في كل اختبار، لها القيم نفسها لـ $N$ و$S$. ستُستدعى الدالة olumsuz_cekirge مرة واحدة لكل سيناريو مستقل.

القيود

• $1\le T\le100$
• $4\le N\le400$
• $1\le S\le4$
• برنامج التقييم غير تكيّفي. بصورة أدق، يُحدَّد الإدخال قبل استدعاء الدالة olumsuz_cekirge ولا يتغير أثناء العمليات.

المهام الفرعية

تكون النقاط المحصلة من المهمة الفرعية ذات الفهرس $i$ مساوية لـ $0$ إذا استُدعيت الدالة kombo بمعاملات لا تستوفي الشروط أعلاه في أي سيناريو، أو إذا أعادت الدالة olumsuz_cekirge نتيجة غير صحيحة. خلاف ذلك، تساوي النقاط الصيغة التالية:

$$P_i\times\min\left(1,\left(\frac{400-q}{400-Q_i}\right)^3\right)$$

• تشير القيمة $P_i$ إلى إجمالي النقاط الممكن الحصول عليها من المهمة الفرعية ذات الفهرس $i$.
• تشير القيمة $q$ إلى أكبر عدد من مرات استدعاء الدالة kombo بين السيناريوهات في جميع اختبارات المهمة الفرعية ذات الفهرس $i$.
• تُعطى قيم $Q_i$ في وصف المهام الفرعية.

أمثلة

olumsuz_cekirge(6, 3)

في الأمثلة، تكون الهجمات المقابلة للأزرار بالترتيب هي ABCBBA، ولذلك يجب أن تعيد هذه الدالة تلك السلسلة.

kombo([0, 1, 2])

يعيد الاستدعاء أعلاه $2$. تكون الهجمات في هذه المجموعة $ABC$. تصيب الهجمة الأولى $A$. تُصد الهجمة $B$. وبما أن آخر هجمة ألحقت ضررًا كانت $A$، فلا تستطيع النملة صد الهجمة $C$، فتتلقى ضررًا.

kombo([0, 0, 0])

يعيد الاستدعاء أعلاه $3$. تكون الهجمات في هذه المجموعة $AAA$. تُلحق جميع هجمات $A$ ضررًا.

kombo([5, 1, 3, 2, 2, 0])

يعيد الاستدعاء أعلاه $3$. تكون الهجمات في هذه المجموعة $ABBCCA$. تصيب الهجمة الأولى $A$. تُصد الهجمة $B$. وبما أن آخر هجمة أصابت لا تزال $A$، تُصد الهجمة الثانية $B$ أيضًا. تُلحق هجمتا $C$ الأولى والثانية ضررًا. وبما أن آخر هجمة أصابت هي $C$، تتوقع النملة الخصم $A$، ولذلك تُصد الهجمة الأخيرة $A$.

kombo([2, 2, 1])

يعيد الاستدعاء أعلاه $3$. تكون الهجمات في هذه المجموعة $CCB$. تُلحق جميع الهجمات ضررًا.

برنامج التقييم النموذجي

يقرأ برنامج التقييم النموذجي الإدخال بالصيغة التالية، حيث $C_i$ سلسلة طولها $N$ تمثل الهجمات السرية للأزرار في السيناريو ذي الفهرس $i$:

$$\begin{gathered}T\ N\ S\\C_1\\C_2\\\ldots\\C_T\end{gathered}$$

سيطبع ما يلي لكل سيناريو: إذا حُلّ السيناريو بشكل صحيح، يُطبع إجمالي عدد العمليات المستخدمة. وإذا وقع أي خطأ، تُطبع إحدى رسائل الخطأ التالية:

Yanlis cevap (Wrong answer)
Buton asildi (Button limit exceeded)
Yanlis buton (Invalid button)
Kombo asildi (Combo limit exceeded)

• Yanlis cevap (إجابة خاطئة): تُطبع إذا كان هناك خطأ في الإجابة لأي زر.
• Buton asildi (تجاوز حد الأزرار): تُعاد إذا استُخدم أكثر من $400$ زر في استدعاء واحد للدالة kombo.
• Yanlis buton (زر غير صالح): تُعاد إذا لم يكن أحد فهارس الأزرار عددًا بين $0$ و$N-1$ في استدعاء للدالة kombo.
• Kombo asildi (تجاوز حد مجموعات الهجمات): تُعاد إذا استُدعيت الدالة kombo أكثر من $400$ مرة خلال استدعاء واحد للدالة olumsuz_cekirge.