Mehmet, חובב משחקי מחשב, משחק ב־Immortal Grasshopper כבר 10 שעות. Immortal Grasshopper הוא משחק מחשב שבו אתם שולטים באמצעות כפתורים בדמות שלכם, חגב שהוא אמן קראטה. היריב העומד מולכם הוא נמלה הנשלטת בידי המחשב.

החגב יכול לבצע בסך הכול $S$ סוגי התקפות שונים ($1\le S\le4$). התקפות אלה נקראות על שם $S$ האותיות הראשונות באלפבית. למשל:

• כאשר $S=2$: שמות ההתקפות הם $A,B$.
• כאשר $S=4$: שמות ההתקפות הם $A,B,C,D$.

כל התקפה שפוגעת ביריב גורמת נזק של 1.

אף שאתם מכירים את כללי המשחק, 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)$ ולא תגרמו נזק. אם היא אינה יכולה לחסום, תגרמו לנמלה נזק של 1 (ההתקפה הראשונה תמיד גורמת נזק).

מטרתכם היא לגלות ולדווח אילו התקפות מבצעים כל הכפתורים, תוך שימוש במספר כולל מזערי של קומבואים.

פרטי מימוש

עליכם לממש את הפונקציה הבאה:

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{array}{l} T\ N\ S\\ C_1\\ C_2\\ \ldots\\ C_T \end{array} $$

לכל תרחיש היא תדפיס את הדברים הבאים: אם התרחיש נפתר נכון, יודפס מספר הפעולות הכולל שנעשה בו שימוש. אם יש שגיאה כלשהי, תודפס אחת מהודעות השגיאה הבאות:

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

• Yanlis cevap (Wrong answer) — תשובה שגויה: מודפסת אם יש טעות בתשובה עבור כפתור כלשהו.
• Buton asildi (Button limit exceeded) — חריגה ממגבלת הכפתורים: מוחזרת אם נעשה שימוש ביותר מ־400 כפתורים בקריאה אחת לפונקציה kombo.
• Yanlis buton (Invalid button) — כפתור לא תקין: מוחזרת אם אחד ממספרי הכפתורים בקריאה לפונקציה kombo אינו מספר בין $0$ ל־$N-1$.
• Kombo asildi (Combo limit exceeded) — חריגה ממגבלת הקומבואים: מוחזרת אם הפונקציה kombo נקראת יותר מ־400 פעמים במהלך קריאה אחת לפונקציה olumsuz_cekirge.