CF379D New Year Letter

许多国家在新年或圣诞节都有写信给圣诞老人的传统，信中包含了愿望清单。Vasya 是一个普通的程序员男孩。像所有普通的孩子一样，他打算在新年除夕写信给圣诞老人（在俄罗斯，我们实际上是在新年期待圣诞老人，而不是在圣诞节）。 Vasya 想出了一个他写信时要遵循的算法。首先，他选择两个仅包含大写英文字母的字符串 $s_1$ 和 $s_2$。然后他利用递推式 $s_n = s_{n-2} + s_{n-1}$ 来生成字符串 $s_k$，其中加号“$+$”表示字符串按顺序连接。最后，Vasya 把生成的 $s_k$ 抄写在纸上，放进信封，寄给圣诞老人。 Vasya 坚信，如果最终的字符串 $s_k$ 中恰好包含 $x$ 个子串 AC（这让他想起了被接受过的题目），圣诞老人就会送给他最好的礼物。另外，Vasya 决定 $s_1$ 的长度必须是 $n$，$s_2$ 的长度必须是 $m$。除此之外，他没有其他的要求。 现在 Vasya 突然有了紧急的新年事务，于是请你帮他选择符合要求的 $s_1$ 和 $s_2$。请帮帮 Vasya。

第一行包含四个整数 $k, x, n, m$，满足 $3 \leq k \leq 50$，$0 \leq x \leq 10^9$，$1 \leq n, m \leq 100$。

第一行输出长度为 $n$ 的字符串 $s_1$，由大写英文字母组成。 第二行输出长度为 $m$ 的字符串 $s_2$，由大写英文字母组成。 如果存在多个满足条件的解，你可以输出任意一个。 如果不存在满足条件的字符串对，输出 “Happy new year!”（不加引号）。

由 ChatGPT 5 翻译