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$ — число различных типов атак в игре.
• Функция должна вернуть строку типа string длины $N$, описывающую атаки, назначенные кнопкам.

При этом можно использовать следующую функцию kombo:

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

• Во время каждого вызова olumsuz_cekirge функцию kombo можно вызывать не более $400$ раз.
• Массив buton задаёт индексы кнопок, которые вы хотите использовать в комбо.
• Элементы массива buton должны быть целыми числами от $0$ до $N - 1$.
• Длина массива buton не должна превышать $400$.

В каждом тесте необходимо решить $T$ независимых сценариев с одинаковыми значениями $N$ и $S$. Для каждого независимого сценария функция olumsuz_cekirge будет вызвана один раз.

Ограничения

• $1 \le T \le 100$
• $4 \le N \le 400$
• $1 \le S \le 4$
• Проверяющая программа не адаптивна. Точнее, входные данные фиксируются до вызова функции olumsuz_cekirge и не меняются во время выполнения операций.

Подзадачи

Количество баллов за $i$-ю подзадачу будет равно $0$, если хотя бы в одном сценарии функция kombo вызвана с параметрами, не удовлетворяющими приведённым выше требованиям, или функция olumsuz_cekirge возвращает неправильный результат. В противном случае оно вычисляется по формуле:

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

• $P_i$ — максимальное количество баллов, которое можно получить за $i$-ю подзадачу.
• $q$ — максимальное число вызовов функции kombo среди сценариев во всех тестах $i$-й подзадачи.
• Значения $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$ — строка длины $N$, задающая скрытые атаки кнопок в $i$-м сценарии:

$$\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 (Wrong answer): выводится, если ответ хотя бы для одной кнопки неверен.
• Buton asildi (Button limit exceeded): возвращается, если в одном вызове функции kombo используется более $400$ кнопок.
• Yanlis buton (Invalid button): возвращается, если в вызове функции kombo хотя бы один индекс кнопки не является числом от $0$ до $N - 1$.
• Kombo asildi (Combo limit exceeded): возвращается, если во время одного вызова функции olumsuz_cekirge функция kombo вызывается более $400$ раз.