Mehmet, que adora jogos de computador, está a jogar Immortal Grasshopper há 10 horas. Immortal Grasshopper é um jogo de computador em que controla a sua personagem, um gafanhoto mestre de karaté, através de botões. O adversário que enfrenta é uma formiga controlada pelo computador.

O gafanhoto pode executar um total de $S$ ($1\le S\le 4$) ataques diferentes. Estes ataques têm os nomes das primeiras $S$ letras do alfabeto. Por exemplo:

• $S=2$: os ataques chamam-se $A,B$.
• $S=4$: os ataques chamam-se $A,B,C,D$.

Cada ataque que atinge o adversário causa 1 ponto de dano.

Embora conheça as regras do jogo, como Mehmet adormeceu depois de jogar durante 10 horas, não há ninguém para lhe ensinar os controlos. Encontrou um comando com $N$ botões na mesa (os botões são numerados de $0$ a $N-1$). Depois de jogar durante algum tempo, percebeu que cada botão pode executar um dos $S$ ataques diferentes, mas não sabe o que faz cada botão. Felizmente, graças ao autocolante no primeiro botão, vê que ele executa um ataque do tipo $A$. Além disso, sabe que cada tipo de ataque diferente está atribuído a pelo menos um botão.

A tarefa que lhe é dada é determinar, jogando este jogo, que tipo de ataque executa cada botão do comando.

Joga como descrito abaixo. Para atacar a formiga adversária, utiliza combinações consecutivas de botões chamadas combos. Um combo funciona da seguinte forma:

• Cria um combo premindo qualquer quantidade de botões em sequência.
• Pode premir os botões em qualquer ordem dentro de um combo.
• O mesmo botão pode ser premido várias vezes num combo.
• Um combo pode ter um comprimento máximo de $400$.

O jogo recebe os seus movimentos e, no fim, mostra-lhe o dano total que causou.

A quantidade de dano que um combo causa à formiga é calculada da seguinte forma. Seja $t(X)$ o ataque que vem imediatamente a seguir ao ataque $X$ por ordem alfabética. Para o ataque representado pela última letra, o valor $t(X)$ é definido como o ataque $A$. Por exemplo:

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

A formiga adversária pode contrariar alguns dos seus ataques com táticas furtivas. Mais precisamente, se utilizou o ataque $X$ como último ataque bem-sucedido (não bloqueado) que causou dano e utilizar o ataque $t(X)$ como ataque seguinte, a formiga bloqueará esse ataque $t(X)$ e não causará dano. Se não o conseguir bloquear, causará 1 ponto de dano à formiga (o primeiro ataque causa sempre dano).

O seu objetivo é descobrir e indicar que ataques executam todos os botões, utilizando o menor número total de combos.

Detalhes de implementação

Deve implementar a seguinte função:

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

• O valor $N$ representa o número de botões do comando.
• O valor $S$ representa o número de tipos de ataques diferentes no jogo.
• Esta função deve devolver uma cadeia de comprimento $N$ que representa os ataques atribuídos aos botões.

Para o fazer, pode utilizar a função kombo abaixo:

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

• Pode chamar a função kombo no máximo $400$ vezes durante cada chamada de olumsuz_cekirge.
• O vetor buton especifica os índices dos botões que pretende utilizar no combo.
• Os valores do vetor buton devem ser inteiros de $0$ a $N-1$.
• O comprimento do vetor buton pode ser, no máximo, $400$.

Deve resolver $T$ cenários independentes em cada teste, com os mesmos valores $N$ e $S$. Para cada cenário independente, a função olumsuz_cekirge será chamada uma vez.

Restrições

• $1\le T\le 100$.
• $4\le N\le 400$.
• $1\le S\le 4$.
• O avaliador não é adaptativo. Mais precisamente, a entrada é fixada antes de a função olumsuz_cekirge ser chamada e não muda durante as operações.

Subtarefas e pontuação

A pontuação obtida na subtarefa $i$ será $0$ se, em qualquer cenário, a função kombo for chamada com parâmetros que não satisfazem os critérios acima, ou se a função olumsuz_cekirge devolver um resultado incorreto. Caso contrário, será igual à seguinte fórmula:

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

• O valor $P_i$ indica o total de pontos possíveis que podem ser obtidos na subtarefa $i$.
• O valor $q$ indica o número máximo de chamadas da função kombo entre os cenários de todos os testes da subtarefa $i$.
• Os valores $Q_i$ são dados nas descrições das subtarefas.

Exemplos

olumsuz_cekirge(6, 3)

Nos exemplos, os ataques correspondentes a cada botão são, por ordem, ABCBBA, pelo que esta função deve devolver essa cadeia.

kombo([0, 1, 2])

A chamada acima devolve $2$. Os ataques deste combo seriam $ABC$. O primeiro ataque $A$ acerta. O ataque $B$ é bloqueado. Como o último ataque que causou dano foi $A$, a formiga não consegue bloquear o ataque $C$ e sofre dano.

kombo([0, 0, 0])

A chamada acima devolve $3$. Os ataques deste combo seriam $AAA$. Todos os ataques $A$ causam dano.

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

A chamada acima devolve $3$. Os ataques deste combo seriam $ABBCCA$. O primeiro ataque $A$ acerta. O ataque $B$ é bloqueado. Como o último ataque que acertou continua a ser $A$, o segundo ataque $B$ também é bloqueado. O primeiro e o segundo ataques $C$ causam dano. Como o último ataque que acertou é $C$, a formiga adversária espera $A$; portanto, o ataque $A$ final é bloqueado.

kombo([2, 2, 1])

A chamada acima devolve $3$. Os ataques deste combo seriam $CCB$. Todos os ataques causam dano.

Avaliador de exemplo

O avaliador de exemplo lê as entradas no seguinte formato, em que $C_i$ é uma cadeia de tamanho $N$ que representa os ataques secretos dos botões no cenário $i$:

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

Imprimirá o seguinte para cada cenário: se o cenário for resolvido corretamente, imprime o número total de operações utilizadas. Se houver algum erro, imprime uma das seguintes mensagens de erro:

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

• Yanlis cevap (Resposta incorreta): impressa se houver um erro na resposta de qualquer botão.
• Buton asildi (Limite de botões excedido): devolvida se forem utilizados mais de $400$ botões numa única chamada da função kombo.
• Yanlis buton (Botão inválido): devolvida se um dos índices dos botões não for um número entre $0$ e $N-1$ numa chamada da função kombo.
• Kombo asildi (Limite de combos excedido): devolvida se a função kombo for chamada mais de $400$ vezes durante uma única chamada da função olumsuz_cekirge.