Алиса много лет поднималась по корпоративной лестнице и наконец достигла самой вершины. Она только что стала генеральным директором (CEO) крупной публичной компании. Предыдущий CEO был уволен из-за плохих финансовых показателей, но Алиса прекрасно знает, как увеличить прибыль. Пора выбрать новое название компании!
Инвесторы обожают любые упоминания искусственного интеллекта, особенно в названии компании. Базовая стоимость компании равна длине её названия, а каждое вхождение подстроки «AI» умножает стоимость компании на 5. Например, название «AAICPCAIIA» имеет длину 10 и два (подчёркнутых) вхождения «AI»:
- $\operatorname{value}(\texttt{AAICPCAIIA}) = 10 \cdot 5 \cdot 5 = 250$
Ещё примеры:
- $\operatorname{value}(\texttt{AXI}) = 3$ (ноль вхождений «
AI») - $\operatorname{value}(\texttt{AIAIAIAI}) = 8 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5000$ (четыре вхождения «
AI») - $\operatorname{value}(\texttt{AIMPPZ}) = 6 \cdot 5 = 30$ (одно вхождение «
AI»)
Контракт Алисы гарантирует ей исключительно щедрый бонус, если стоимость компании будет равна ровно $n$. Кроме того, она хочет, чтобы название было как можно короче.
Алиса уже занята своей следующей задачей — разработкой обновлённого логотипа. Можете ли вы тем временем предложить новое название компании? Найдите кратчайшее возможное слово стоимости $n$, состоящее из заглавных английских букв A-Z.
Входные данные
Единственная строка содержит целое число $n$ ($1 \le n \le 100\,000$) — желаемую стоимость компании.
Выходные данные
Выведите слово, состоящее из букв A-Z — название стоимости $n$ наименьшей возможной длины. Если решений несколько, выведите любое из них.
Примеры
Входные данные 1
30
Выходные данные 1
AIMPPZ
Входные данные 2
250
Выходные данные 2
AAICPCAIIA
Примечание
В первом тесте мы ищем кратчайшее возможное название стоимости 30. Оптимальные слова имеют длину 6 и одно вхождение «AI», например «AIMPPZ», «HUAWAI», «BRAINS» и «AAAIII». Никакое более короткое слово не имеет стоимости 30.
Во втором тесте стоимость 250 невозможно получить с помощью названия короче 10 символов.