D. Новогоднее письмо
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во многих странах есть новогодняя традиция — писать письма дедушке Морозу со своими пожеланиями подарков на новый год. Вася — обыкновенный мальчик-программист. Как все обыкновенные мальчики, он в канун нового года собирается написать письмо дедушке Морозу.

Вася уже придумал алгоритм, по которому он будет писать письмо. Сначала он выберет две строки s1 и s2, состоящие из прописных латинских букв. Далее мальчик составит строку sk, пользуясь рекуррентным соотношением sn = sn - 2 + sn - 1, операция '+' обозначает конкатенацию (то есть последовательную запись) строк в заданном порядке. После чего Вася запишет строку sk на листочек, положит его в письмо и пошлет письмо деду Морозу.

Вася точно уверен: чтобы дед Мороз подарил ему самый лучший подарок, нужно чтобы в полученной строке sk подстрока AC встречалась ровно x раз (сокращение AC напоминает Васе о сданных задачах). Более того, Вася решил, что строка s1 должна иметь длину n, а строка s2 — длину m. Больше Вася ничего не решил.

У Васи сейчас срочные новогодние дела, поэтому он просит вас выбрать для него две строки s1 и s2 требуемым образом. Помогите Васе.

Входные данные

В первой строке записано четыре целых числа k, x, n, m (3 ≤ k ≤ 50; 0 ≤ x ≤ 109; 1 ≤ n, m ≤ 100).

Выходные данные

В первой строке выведите строку s1, состоящую из n заглавных латинских букв. Во второй строке выведите строку s2, состоящую из m заглавных латинских букв. Если существует несколько подходящих строк, разрешается вывести любую.

Если требуемой пары строк не существует, выведите «Happy new year!» без кавычек.

Примеры
Входные данные
3 2 2 2
Выходные данные
AC
AC
Входные данные
3 3 2 2
Выходные данные
Happy new year!
Входные данные
3 0 2 2
Выходные данные
AA
AA
Входные данные
4 3 2 1
Выходные данные
Happy new year!
Входные данные
4 2 2 1
Выходные данные
Happy new year!