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"，圣诞老人就会把他最好的礼物(译者注：什么意思不作解释了，愿各位AC++）给他。除此之外，Vasya 只是确定了 $s_1$ 长度为 $n$, $s_2$ 长度为 $m$，并没有想好他们是什么。 此时，Vasya得到了一件紧急的新年公事，所以他希望让你来帮他选择 $s_1,s_2$，完成他的心愿。 请帮助他。 输入： 第一行四个整数，$k,x,n,m$，意义如前。($3 \le k \le 50,0 \le x \le 10^9, 1 \le n, m \le 100$). 输出： 两行，第一行 $s_1$,第一行 $s_2$，代表两个字符串。 如果不存在这样的两个字符串，输出 `Happy new year!`。

题目描述

Many countries have such a New Year or Christmas tradition as writing a letter to Santa including a wish list for presents. Vasya is an ordinary programmer boy. Like all ordinary boys, he is going to write the letter to Santa on the New Year Eve (we Russians actually expect Santa for the New Year, not for Christmas). Vasya has come up with an algorithm he will follow while writing a letter. First he chooses two strings, $ s_{1} $ anf $ s_{2} $ , consisting of uppercase English letters. Then the boy makes string $ s_{k} $ , using a recurrent equation $ s_{n}=s_{n-2}+s_{n-1} $ , operation '+' means a concatenation (that is, the sequential record) of strings in the given order. Then Vasya writes down string $ s_{k} $ on a piece of paper, puts it in the envelope and sends in to Santa. Vasya is absolutely sure that Santa will bring him the best present if the resulting string $ s_{k} $ has exactly $ x $ occurrences of substring AC (the short-cut reminds him оf accepted problems). Besides, Vasya decided that string $ s_{1} $ should have length $ n $ , and string $ s_{2} $ should have length $ m $ . Vasya hasn't decided anything else. At the moment Vasya's got urgent New Year business, so he asks you to choose two strings for him, $ s_{1} $ and $ s_{2} $ in the required manner. Help Vasya.

输入输出格式

输入格式

The first line contains four integers $ k,x,n,m $ $ (3<=k<=50; 0<=x<=10^{9}; 1<=n,m<=100) $ .

输出格式

In the first line print string $ s_{1} $ , consisting of $ n $ uppercase English letters. In the second line print string $ s_{2} $ , consisting of $ m $ uppercase English letters. If there are multiple valid strings, print any of them. If the required pair of strings doesn't exist, print "Happy new year!" without the quotes.

输入输出样例

输入样例 #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!