Mehmet liebt Computerspiele und spielt seit 10 Stunden Immortal Grasshopper. Immortal Grasshopper ist ein Computerspiel, in dem du deine Figur, einen Heuschrecken-Karatemeister, mit Tasten steuerst. Dein Gegner ist eine computergesteuerte Ameise.

Die Heuschrecke kann insgesamt $S$ ($1\le S\le4$) verschiedene Angriffe ausführen. Diese Angriffe werden mit den ersten $S$ Buchstaben des Alphabets bezeichnet. Zum Beispiel:

• $S=2$: Die Angriffe heißen $A,B$.
• $S=4$: Die Angriffe heißen $A,B,C,D$.

Jeder Angriff, der den Gegner trifft, verursacht $1$ Schaden.

Obwohl du die Spielregeln kennst, gibt es niemanden, der dir die Steuerung erklärt, denn Mehmet ist nach 10 Stunden Spielen eingeschlafen. Auf dem Tisch hast du einen Controller mit $N$ Tasten gefunden (die Tasten sind von $0$ bis $N-1$ nummeriert). Nach einiger Zeit Spielen hast du erkannt, dass jede Taste einen der $S$ verschiedenen Angriffe ausführt, aber du weißt nicht, welche Taste was tut. Zum Glück erkennst du am Aufkleber auf der allerersten Taste, dass sie einen Angriff vom Typ $A$ ausführt. Außerdem weißt du, dass jeder verschiedene Angriffstyp mindestens einer Taste zugeordnet ist.

Deine Aufgabe besteht darin, durch Spielen herauszufinden, welche Angriffsarten alle Tasten des Controllers ausführen.

Du spielst wie folgt. Um die gegnerische Ameise anzugreifen, verwendest du aufeinanderfolgende Tastenkombinationen, sogenannte Kombos. Eine Kombo funktioniert so:

• Du erstellst eine Kombo, indem du beliebig viele Tasten nacheinander drückst.
• Innerhalb einer Kombo kannst du die Tasten in beliebiger Reihenfolge drücken.
• Dieselbe Taste kann in einer Kombo mehrfach gedrückt werden.
• Eine Kombo darf höchstens die Länge $400$ haben.

Das Spiel verarbeitet deine Züge und zeigt dir schließlich den insgesamt verursachten Schaden an.

Der Schaden einer Kombo an der Ameise wird wie folgt berechnet. Sei $t(X)$ der Angriff, der im Alphabet unmittelbar auf Angriff $X$ folgt. Für den durch den letzten Buchstaben dargestellten Angriff wird $t(X)$ als Angriff $A$ definiert. Zum Beispiel:

• Für $S=4$: $t(A)=B,t(B)=C,t(C)=D,t(D)=A$.
• Für $S=2$: $t(A)=B,t(B)=A$.

Die gegnerische Ameise kann mit hinterhältigen Taktiken einige deiner Angriffe abwehren. Genauer: Wenn dein letzter erfolgreicher (nicht abgewehrter) Angriff, der Schaden verursacht hat, Angriff $X$ war und du als nächsten Angriff $t(X)$ verwendest, wehrt die Ameise deinen Angriff $t(X)$ ab und du verursachst keinen Schaden. Kann sie nicht abwehren, verursachst du $1$ Schaden an der Ameise (der erste Angriff verursacht immer Schaden).

Dein Ziel ist es, mit einer möglichst geringen Gesamtzahl an Kombos herauszufinden und anzugeben, welche Angriffe alle Tasten ausführen.

Implementierungsdetails

Du sollst die folgende Funktion implementieren:

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

• Der Wert $N$ gibt die Anzahl der Tasten des Controllers an.
• Der Wert $S$ gibt die Anzahl der verschiedenen Angriffstypen im Spiel an.
• Diese Funktion soll eine Zeichenkette der Länge $N$ zurückgeben, die die den Tasten zugeordneten Angriffe darstellt.

Dabei kannst du die folgende Funktion kombo verwenden:

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

• Während jedes Aufrufs von olumsuz_cekirge darfst du die Funktion kombo höchstens $400$-mal aufrufen.
• Das Array buton gibt die Indizes der Tasten an, die du in der Kombo verwenden möchtest.
• Die Werte des Arrays buton müssen ganze Zahlen von $0$ bis $N-1$ sein.
• Die Länge des Arrays buton darf höchstens $400$ sein.

In jedem Test sollst du $T$ unabhängige Szenarien mit denselben Werten $N$ und $S$ lösen. Für jedes unabhängige Szenario wird die Funktion olumsuz_cekirge einmal aufgerufen.

Beschränkungen

• $1\le T\le100$
• $4\le N\le400$
• $1\le S\le4$
• Der Grader ist nicht adaptiv. Genauer: Die Eingabe steht vor dem Aufruf der Funktion olumsuz_cekirge fest und ändert sich während der Operationen nicht.

Teilaufgaben

Die Punktzahl für die $i$-te Teilaufgabe ist $0$, wenn in irgendeinem Szenario die Funktion kombo mit Parametern aufgerufen wird, die die obigen Bedingungen nicht erfüllen, oder wenn olumsuz_cekirge ein falsches Ergebnis zurückgibt. Andernfalls entspricht sie der folgenden Formel:

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

• Der Wert $P_i$ gibt die insgesamt möglichen Punkte der $i$-ten Teilaufgabe an.
• Der Wert $q$ gibt die maximale Anzahl an Aufrufen der Funktion kombo unter den Szenarien aller Tests der $i$-ten Teilaufgabe an.
• Die Werte $Q_i$ sind in den Beschreibungen der Teilaufgaben angegeben.

Beispiele

olumsuz_cekirge(6, 3)

In den Beispielen entsprechen die Angriffe der Tasten der Reihe nach ABCBBA, daher soll diese Funktion diese Zeichenkette zurückgeben.

kombo([0, 1, 2])

Der obige Aufruf gibt $2$ zurück. Die Angriffe dieser Kombo sind $ABC$. Der erste Angriff $A$ trifft. Angriff $B$ wird abgewehrt. Da der letzte Angriff, der Schaden verursacht hat, $A$ war, kann die Ameise Angriff $C$ nicht abwehren und erleidet Schaden.

kombo([0, 0, 0])

Der obige Aufruf gibt $3$ zurück. Die Angriffe dieser Kombo sind $AAA$. Alle Angriffe $A$ verursachen Schaden.

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

Der obige Aufruf gibt $3$ zurück. Die Angriffe dieser Kombo sind $ABBCCA$. Der erste Angriff $A$ trifft. Angriff $B$ wird abgewehrt. Da der letzte treffende Angriff weiterhin $A$ ist, wird auch der zweite Angriff $B$ abgewehrt. Der erste und zweite Angriff $C$ verursachen Schaden. Da der letzte treffende Angriff $C$ ist, erwartet die gegnerische Ameise $A$, weshalb der abschließende Angriff $A$ abgewehrt wird.

kombo([2, 2, 1])

Der obige Aufruf gibt $3$ zurück. Die Angriffe dieser Kombo sind $CCB$. Alle Angriffe verursachen Schaden.

Beispiel-Grader

Der Beispiel-Grader liest die Eingaben im folgenden Format, wobei $C_i$ eine Zeichenkette der Länge $N$ ist, die die geheimen Angriffe der Tasten für das $i$-te Szenario darstellt:

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

Für jedes Szenario gibt er Folgendes aus: Wird das Szenario richtig gelöst, wird die Gesamtzahl der verwendeten Operationen ausgegeben. Bei einem Fehler wird eine der folgenden Fehlermeldungen ausgegeben:

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

• Yanlis cevap (Wrong answer) (falsche Antwort): Wird ausgegeben, wenn die Antwort für irgendeine Taste falsch ist.
• Buton asildi (Button limit exceeded) (Tastenlimit überschritten): Wird zurückgegeben, wenn in einem einzelnen Aufruf von kombo mehr als $400$ Tasten verwendet werden.
• Yanlis buton (Invalid button) (ungültige Taste): Wird zurückgegeben, wenn in einem Aufruf von kombo einer der Tastenindizes keine Zahl zwischen $0$ und $N-1$ ist.
• Kombo asildi (Combo limit exceeded) (Kombo-Limit überschritten): Wird zurückgegeben, wenn kombo während eines einzelnen Aufrufs von olumsuz_cekirge mehr als $400$-mal aufgerufen wird.