← 返回题目列表

Codeforces · 379/D

D. 新年信

中文机器翻译题面 查看原题

许多国家都有新年或圣诞节的传统,比如给圣诞老人写一封信,其中包括一份礼物愿望清单。 Vasya 是一个普通的程序员男孩。和所有普通男孩一样,他要在除夕夜给圣诞老人写信(我们俄罗斯人实际上期待圣诞老人在新年出现,而不是圣诞节)。

Vasya 提出了一种他在写信时将遵循的算法。首先,他选择两个字符串,s1 和 s2,由大写英文字母组成。然后男孩使用循环方程 sn = sn - 2 + sn - 1 制作字符串 sk,操作“+”表示按给定顺序连接字符串(即顺序记录)。然后 Vasya 将字符串 sk 写在一张纸上,放入信封并发送给圣诞老人。

Vasya 绝对确信,如果结果字符串 sk 恰好有 x 次出现子字符串 AC(快捷方式提醒他已接受的问题),圣诞老人会给他带来最好的礼物。此外,Vasya 决定字符串 s1 的长度应为 n,字符串 s2 的长度应为 m。瓦夏还没有做出任何其他决定。

现在Vasya有紧急的新年事务,所以他要求你按照要求的方式为他选择两根弦,s1和s2。帮助瓦夏。

输入

第一行包含四个整数 k、x、n、m (3 ≤ k ≤ 50;0 ≤ x ≤ 109;1 ≤ n,m ≤ 100)。

输出

在第一行打印字符串s1,由n个大写英文字母组成。第二行打印字符串s2,由m个大写英文字母组成。如果有多个有效字符串,则打印其中任何一个。

如果所需的字符串对不存在,则打印“新年快乐!”没有引号。

示例

输入 #1

3 2 2 2

输出 #1

AC
AC

输入 #2

3 3 2 2

输出 #2

Happy new year!

输入 #3

3 0 2 2

输出 #3

AA
AA

输入#4

4 3 2 1

输出#4

Happy new year!

输入 #5

4 2 2 1

输出 #5

Happy new year!