컴퓨터 게임을 좋아하는 Mehmet은 지난 10시간 동안 Immortal Grasshopper를 하고 있습니다. Immortal Grasshopper는 가라테 고수인 메뚜기 캐릭터를 버튼으로 조종하는 컴퓨터 게임입니다. 상대는 컴퓨터가 조종하는 개미입니다.

메뚜기는 총 $S$가지($1\le S\le 4$) 공격을 할 수 있습니다. 공격의 이름은 알파벳의 처음 $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)

• olumsuz_cekirge가 한 번 호출되는 동안 kombo 함수를 최대 $400$번 호출할 수 있습니다.
• buton 배열은 콤보에서 사용할 버튼의 번호를 나타냅니다.
• buton 배열의 값은 $0$부터 $N-1$까지의 정수여야 합니다.
• buton 배열의 길이는 최대 $400$입니다.

각 테스트에서 같은 $N,S$ 값을 가진 독립적인 시나리오 $T$개를 해결해야 합니다. 각 시나리오에 대해 olumsuz_cekirge 함수가 한 번 호출됩니다.

제한

• $1\le T\le 100$
• $4\le N\le 400$
• $1\le S\le 4$
• 채점기는 적응형이 아닙니다. 구체적으로 입력은 olumsuz_cekirge 함수를 호출하기 전에 고정되며 조작 중에 변하지 않습니다.

서브태스크

어떤 시나리오에서든 위 조건에 맞지 않는 매개변수로 kombo 함수를 호출하거나 olumsuz_cekirge 함수가 잘못된 결과를 반환하면 $i$번 서브태스크의 점수는 $0$입니다. 그렇지 않으면 점수는 다음과 같습니다.

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

• $P_i$는 $i$번 서브태스크에서 얻을 수 있는 총점입니다.
• $q$는 $i$번 서브태스크의 모든 테스트에 포함된 시나리오 중 kombo 함수 호출 횟수의 최댓값입니다.
• $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$는 $i$번 시나리오의 버튼에 숨겨진 공격을 나타내는 길이 $N$의 문자열입니다.

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

각 시나리오에 대해 다음을 출력합니다. 시나리오를 올바르게 해결하면 사용한 총 조작 횟수를 출력합니다. 오류가 있으면 다음 오류 메시지 중 하나를 출력합니다.

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

• Yanlis cevap(틀린 답): 어떤 버튼이든 답에 오류가 있으면 출력합니다.
• Buton asildi(버튼 제한 초과): 한 번의 kombo 함수 호출에서 $400$개보다 많은 버튼을 사용하면 반환합니다.
• Yanlis buton(잘못된 버튼): kombo 함수 호출에 포함된 버튼 번호 중 $0$부터 $N-1$까지의 수가 아닌 것이 있으면 반환합니다.
• Kombo asildi(콤보 제한 초과): 한 번의 olumsuz_cekirge 함수 호출 중 kombo 함수를 $400$번보다 많이 호출하면 반환합니다.