许多国家都有新年或圣诞节的传统,比如给圣诞老人写一封信,其中包括一份礼物愿望清单。 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!