Mehmet, qui adore les jeux vidéo, joue à Immortal Grasshopper depuis 10 heures. Immortal Grasshopper est un jeu vidéo où vous contrôlez à l'aide de boutons votre personnage, une sauterelle maître de karaté. Votre adversaire est une fourmi contrôlée par l'ordinateur.

La sauterelle peut effectuer $S$ attaques différentes au total ($1\le S\le 4$). Elles portent les noms des $S$ premières lettres de l'alphabet. Par exemple :

• Pour $S=2$, les attaques s'appellent $A,B$.
• Pour $S=4$, les attaques s'appellent $A,B,C,D$.

Chaque attaque qui touche l'adversaire inflige 1 point de dégâts.

Vous connaissez les règles, mais Mehmet s'est endormi après 10 heures de jeu et personne ne peut vous apprendre les commandes. Vous trouvez sur la table une manette avec $N$ boutons, numérotés de $0$ à $N-1$. Après avoir joué un moment, vous comprenez que chaque bouton déclenche l'une des $S$ attaques, sans savoir laquelle. Heureusement, l'autocollant sur le tout premier bouton indique qu'il déclenche l'attaque $A$. Vous savez aussi que chaque type d'attaque est attribué à au moins un bouton.

Votre tâche consiste à déterminer, en jouant, le type d'attaque déclenché par chaque bouton.

Le jeu se déroule comme suit. Pour attaquer la fourmi, vous utilisez des suites de boutons appelées combos. Un combo fonctionne ainsi :

• Vous créez un combo en appuyant successivement sur un nombre quelconque de boutons.
• Les boutons peuvent être pressés dans n'importe quel ordre dans un combo.
• Le même bouton peut être pressé plusieurs fois dans un combo.
• Un combo peut avoir une longueur maximale de $400$.

Le jeu prend vos actions en compte et vous indique finalement le total des dégâts infligés.

Les dégâts d'un combo sont calculés comme suit. Notons $t(X)$ l'attaque qui suit immédiatement $X$ dans l'ordre alphabétique. Pour l'attaque représentée par la dernière lettre, $t(X)$ est définie comme l'attaque $A$. Par exemple :

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

La fourmi peut contrer certaines attaques par des tactiques sournoises. Plus précisément, si votre dernière attaque réussie (non bloquée) qui a infligé des dégâts est $X$ et que votre attaque suivante est $t(X)$, la fourmi la bloque et vous n'infligez aucun dégât. Si elle ne peut pas la bloquer, vous lui infligez 1 point de dégâts. La première attaque inflige toujours des dégâts.

Votre objectif est de déterminer et de signaler l'attaque de chaque bouton en utilisant le nombre total minimal de combos.

Détails d'implémentation

Vous devez implémenter la fonction suivante :

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

• $N$ représente le nombre de boutons de la manette.
• $S$ représente le nombre de types d'attaques du jeu.
• Cette fonction doit renvoyer une chaîne de longueur $N$ représentant les attaques attribuées aux boutons.

Pour cela, vous pouvez utiliser la fonction kombo suivante :

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

• Vous pouvez appeler kombo au plus $400$ fois pendant chaque appel à olumsuz_cekirge.
• Le tableau buton indique les indices des boutons que vous souhaitez utiliser dans le combo.
• Les valeurs de buton doivent être des entiers de $0$ à $N-1$.
• La longueur de buton ne doit pas dépasser $400$.

Vous devez résoudre $T$ scénarios indépendants dans chaque test, avec les mêmes valeurs de $N$ et de $S$. Pour chacun, olumsuz_cekirge sera appelée une fois.

Contraintes

• $1\le T\le 100$
• $4\le N\le 400$
• $1\le S\le 4$
• L'évaluateur n'est pas adaptatif. Plus précisément, l'entrée est fixée avant l'appel à olumsuz_cekirge et ne change pas pendant les opérations.

Sous-tâches

Le score de la sous-tâche $i$ vaut $0$ si, dans un scénario quelconque, kombo est appelée avec des paramètres qui ne respectent pas les critères ci-dessus, ou si olumsuz_cekirge renvoie un résultat incorrect. Sinon, il vaut :

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

• $P_i$ désigne le nombre total de points possibles pour la sous-tâche $i$.
• $q$ désigne le nombre maximal d'appels à kombo parmi les scénarios de tous les tests de la sous-tâche $i$.
• Les valeurs $Q_i$ sont données dans les descriptions des sous-tâches.

Exemples

olumsuz_cekirge(6, 3)

Dans ces exemples, les attaques des boutons sont, dans l'ordre, ABCBBA : la fonction doit donc renvoyer cette chaîne.

kombo([0, 1, 2])

Cet appel renvoie $2$. Les attaques du combo sont $ABC$. La première attaque $A$ touche. L'attaque $B$ est bloquée. Comme la dernière attaque ayant infligé des dégâts est $A$, la fourmi ne peut pas bloquer $C$ et subit des dégâts.

kombo([0, 0, 0])

Cet appel renvoie $3$. Les attaques sont $AAA$. Toutes les attaques $A$ infligent des dégâts.

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

Cet appel renvoie $3$. Les attaques sont $ABBCCA$. La première attaque $A$ touche. L'attaque $B$ est bloquée. Comme la dernière attaque réussie est toujours $A$, la seconde attaque $B$ est également bloquée. Les deux attaques $C$ infligent des dégâts. La dernière attaque réussie étant $C$, la fourmi attend $A$ et bloque donc la dernière attaque $A$.

kombo([2, 2, 1])

Cet appel renvoie $3$. Les attaques sont $CCB$. Toutes infligent des dégâts.

Évaluateur d'exemple

L'évaluateur d'exemple lit l'entrée au format suivant, où $C_i$ est une chaîne de longueur $N$ représentant les attaques secrètes des boutons du scénario $i$ :

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

Pour chaque scénario, il affiche le nombre total d'opérations utilisées si le scénario est résolu correctement. En cas d'erreur, il affiche l'un des messages suivants :

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

• Yanlis cevap (Wrong answer) : affiché si la réponse pour un bouton quelconque est incorrecte.
• Buton asildi (Button limit exceeded) : renvoyé si plus de $400$ boutons sont utilisés dans un même appel à kombo.
• Yanlis buton (Invalid button) : renvoyé si un indice de bouton d'un appel à kombo n'est pas un nombre compris entre $0$ et $N-1$.
• Kombo asildi (Combo limit exceeded) : renvoyé si kombo est appelée plus de $400$ fois pendant un même appel à olumsuz_cekirge.