Mehmet, che ama i videogiochi, sta giocando a Immortal Grasshopper da 10 ore. Immortal Grasshopper è un videogioco in cui controlli con dei pulsanti il tuo personaggio, una cavalletta maestra di karate. L'avversario che affronti è una formica controllata dal computer.

La cavalletta può eseguire in totale $S$ ($1\le S\le4$) attacchi diversi. Questi attacchi sono chiamati con le prime $S$ lettere dell'alfabeto. Per esempio:

• $S=2$: gli attacchi si chiamano $A,B$.
• $S=4$: gli attacchi si chiamano $A,B,C,D$.

Ogni attacco che colpisce l'avversario infligge 1 punto di danno.

Sebbene tu conosca le regole del gioco, poiché Mehmet si è addormentato dopo aver giocato per 10 ore, non c'è nessuno che ti insegni i comandi. Hai trovato sul tavolo un controller con $N$ pulsanti (numerati da $0$ a $N-1$). Dopo aver giocato per un po', hai capito che ogni pulsante può eseguire uno dei $S$ diversi attacchi, ma non sai quale pulsante faccia cosa. Fortunatamente, grazie all'adesivo sul primo pulsante, vedi che esegue un attacco di tipo $A$. Inoltre, sai che ogni diverso tipo di attacco è assegnato ad almeno un pulsante.

Il tuo compito è determinare, giocando, quali tipi di attacco eseguono tutti i pulsanti del controller.

Giochi nel modo descritto di seguito. Per attaccare la formica avversaria, usi sequenze di pulsanti chiamate combo. Una combo funziona così:

• Crei una combo premendo in sequenza un numero qualsiasi di pulsanti.
• Puoi premere i pulsanti in qualsiasi ordine all'interno di una combo.
• Lo stesso pulsante può essere premuto più volte in una combo.
• Una combo può avere una lunghezza massima di 400.

Il gioco riceve le tue mosse e alla fine ti mostra il danno totale che hai inflitto.

Il danno che una combo infligge alla formica viene calcolato come segue. Sia $t(X)$ l'attacco che segue immediatamente l'attacco $X$ in ordine alfabetico. Per l'attacco rappresentato dall'ultima lettera, $t(X)$ è definito come l'attacco $A$. Per esempio:

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

La formica avversaria può contrastare alcuni dei tuoi attacchi usando tattiche subdole. Più precisamente, se il tuo ultimo attacco riuscito (non bloccato) che ha inflitto danno è stato $X$, e usi come attacco successivo $t(X)$, la formica bloccherà l'attacco $t(X)$ e non infliggerai danno. Se non può bloccarlo, infliggerai 1 punto di danno alla formica (il primo attacco infligge sempre danno).

Il tuo obiettivo è scoprire e riportare quali attacchi eseguono tutti i pulsanti usando il minor numero totale di combo.

Dettagli di implementazione

Devi implementare la seguente funzione:

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

• $N$ rappresenta il numero di pulsanti del controller.
• $S$ rappresenta il numero di diversi tipi di attacco nel gioco.
• Questa funzione deve restituire una stringa di lunghezza $N$ che rappresenta gli attacchi assegnati ai pulsanti.

Per farlo, puoi usare la funzione kombo seguente:

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

• Puoi chiamare la funzione kombo al massimo 400 volte durante ciascuna chiamata a olumsuz_cekirge.
• L'array buton specifica gli indici dei pulsanti che vuoi usare nella combo.
• I valori dell'array buton devono essere interi da $0$ a $N-1$.
• La lunghezza dell'array buton può essere al massimo 400.

Devi risolvere $T$ scenari indipendenti in ciascun test, con gli stessi valori di $N$ e $S$. Per ogni scenario indipendente, la funzione olumsuz_cekirge verrà chiamata una volta.

Vincoli

• $1\le T\le100$.
• $4\le N\le400$.
• $1\le S\le4$.
• Il grader non è adattivo. Più precisamente, l'input viene fissato prima della chiamata alla funzione olumsuz_cekirge e non cambia durante le operazioni.

Sottoproblemi e punteggio

Il punteggio ottenuto nel sottoproblema $i$ sarà $0$ se, in qualunque scenario, la funzione kombo viene chiamata con parametri che non rispettano i criteri precedenti, oppure se la funzione olumsuz_cekirge restituisce un risultato errato. Altrimenti, sarà uguale alla seguente formula:

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

• $P_i$ indica il punteggio totale possibile del sottoproblema $i$.
• $q$ indica il massimo numero di chiamate alla funzione kombo tra gli scenari di tutti i test del sottoproblema $i$.
• I valori $Q_i$ sono riportati nelle descrizioni dei sottoproblemi.

Esempi

olumsuz_cekirge(6, 3)

Negli esempi, gli attacchi corrispondenti ai pulsanti, nell'ordine, sono ABCBBA, quindi questa funzione deve restituire tale stringa.

kombo([0, 1, 2])

La chiamata sopra restituisce $2$. Gli attacchi di questa combo sono $ABC$. Il primo attacco $A$ colpisce. L'attacco $B$ viene bloccato. Poiché l'ultimo attacco che ha inflitto danno è stato $A$, la formica non può bloccare l'attacco $C$ e subisce danno.

kombo([0, 0, 0])

La chiamata sopra restituisce $3$. Gli attacchi di questa combo sono $AAA$. Tutti gli attacchi $A$ infliggono danno.

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

La chiamata sopra restituisce $3$. Gli attacchi di questa combo sono $ABBCCA$. Il primo attacco $A$ colpisce. L'attacco $B$ viene bloccato. Poiché l'ultimo attacco andato a segno è ancora $A$, anche il secondo attacco $B$ viene bloccato. Il primo e il secondo attacco $C$ infliggono danno. Poiché l'ultimo attacco andato a segno è $C$, la formica avversaria si aspetta $A$, quindi l'ultimo attacco $A$ viene bloccato.

kombo([2, 2, 1])

La chiamata sopra restituisce $3$. Gli attacchi di questa combo sono $CCB$. Tutti gli attacchi infliggono danno.

Grader di esempio

Il grader di esempio legge l'input nel seguente formato, dove $C_i$ è una stringa di lunghezza $N$ che rappresenta gli attacchi segreti dei pulsanti nello scenario $i$:

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

Per ciascuno scenario stamperà quanto segue: se lo scenario viene risolto correttamente, viene stampato il numero totale di operazioni usate. Se si verifica un errore, viene stampato uno dei seguenti messaggi di errore:

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

• Yanlis cevap (Wrong answer): viene stampato se la risposta è errata per un qualunque pulsante.
• Buton asildi (Button limit exceeded): viene restituito se si usano più di 400 pulsanti in una singola chiamata alla funzione kombo.
• Yanlis buton (Invalid button): viene restituito se uno degli indici dei pulsanti in una chiamata alla funzione kombo non è un numero tra $0$ e $N-1$.
• Kombo asildi (Combo limit exceeded): viene restituito se la funzione kombo viene chiamata più di 400 volte durante una singola chiamata alla funzione olumsuz_cekirge.