D. Шинэ жилийн захидал

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Олон оронд Шинэ жилийн эсвэл Зул сарын баяраар өөрийн хүслийн захидлаа Сантаруу илгээдэг. Васья бол ердийн л программер хөвгүүн. Яг л бусад энгийн хөвгүүд шиг. Тиймээс тэр Шинэ жилийн өмнөх өдөр Сантаруу захидал бичих гэж байгаа.

Васья захидал бичихдээ мөрдөх алгоритмтай. Тэрээр $s_1$, $s_2$ гэсэн Англи хэлний том үсгээр бичигдсэн үг сонгоод $s_n\ =\ s_{n - 2}\ +\ s_{n - 1}$ үйлдлээр $('+'$ гэдэг нь өгөгдсөн дарааллаар нь залгахыг хэлнэ$)$ $s_k$ гэсэн үгийг үүсгэж Сантаруу илгээнэ.

Васья хэрвээ бичсэн $s_k$ нь дотроо яг $x$ ширхэг $AC$ агуулж байвал Санта түүнд хамгийн гоё бэлэг өгөн гэдэгт итгэлтэй байгаа. Тэрээр $s_1$ үг нь $n$ урттай, $s_2$ үг нь $m$ урттай байна гэснээс өөр зүйл шийдээгүй байгаа.

Яг энэ үед Васья шинэ жилийн хойшлуулашгүй ажилтай болсон бөгөөд танаас тэдгээр 2 үгийг сонгож тус болохыг хүсчээ. Түүнд туслана уу.

Оролт

Нэг мөрөнд $k$, $x$, $n$, $m$ $(3\ ≤\ k\ ≤\ 50;\ 0\ ≤\ x\ ≤\ 10^9;\ 1\ ≤\ n,m\ ≤\ 100)$ өгөгдөнө.

Гаралт

Эхний мөрөнд $n$ урттай $s_1$ үгийг, дараагийн мөрөнд $m$ урттай $s_2$ үгийг хэвлэнэ. Боломжит үг олон байвал дурын нэгийг нь хэвлэ.

Хэрвээ боломжит үг олдохгүй бол "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!
Сэтгэгдлүүдийг ачааллаж байна...