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, s1 anf s2, consisting of uppercase English letters. Then the boy makes string sk, using a recurrent equation sn = sn - 2 + sn - 1, operation '+' means a concatenation (that is, the sequential record) of strings in the given order. Then Vasya writes down string sk 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 sk has exactly x occurrences of substring AC (the short-cut reminds him оf accepted problems). Besides, Vasya decided that string s1 should have length n, and string s2 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, s1 and s2 in the required manner. Help Vasya.

Input

The first line contains four integers k, x, n, m (3 ≤ k ≤ 50; 0 ≤ x ≤ 109; 1 ≤ n, m ≤ 100).

Output

In the first line print string s1, consisting of n uppercase English letters. In the second line print string s2, 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.

Examples

Input

3 2 2 2


Output

AC
AC


Input

3 3 2 2


Output

Happy new year!


Input

3 0 2 2


Output

AA
AA


Input

4 3 2 1


Output

Happy new year!


Input

4 2 2 1


Output

Happy new year!

Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Complete search
Skill types: Dynamic programming

Bit manipulation

Complete search

Starter code:

Solutions:
def main():
	(k, x, n, m) = map(int, input().split())

	def f(s, e, n, cnt):
		ret = [''] * n
		ret[0] = s
		ret[-1] = e
		sa = 0 if s == 'A' else 1
		for i in range(cnt):
			ret[sa] = 'A'
			ret[sa + 1] = 'C'
			sa += 2
		for j in range(sa, n - 1):
			ret[j] = 'B'
		return ''.join(ret)
	for sa in 'ABC':
		for ea in 'ABC':
			if n == 1:
				ea = sa
			for sb in 'ABC':
				for eb in 'ABC':
					if m == 1:
						eb = sb
					N = max(0, n - (sa != 'A') - (ea != 'C'))
					M = max(0, m - (sb != 'A') - (eb != 'C'))
					for i in range(1 + N // 2):
						for j in range(1 + M // 2):
							A = sa + ea
							B = sb + eb
							(a, b) = (i, j)
							for c in range(k - 2):
								(a, b) = (b, a + b)
								if A[1] == 'A' and B[0] == 'C':
									b += 1
								(A, B) = (B, A[0] + B[1])
							if b == x:
								print(f(sa, ea, n, i))
								print(f(sb, eb, m, j))
								return 0
	print('Happy new year!')
	return 0
main()


import sys
import itertools
(k, x, n, m) = map(int, input().split())

def valid(inicio, fim, tamanho, num_ac):
	if num_ac == 0:
		if tamanho == 1:
			return '' if inicio != fim else inicio
		elif tamanho == 2:
			return inicio + fim if inicio + fim != 'AC' else ''
		else:
			return inicio + 'B' * (tamanho - 2) + fim
	s = 'AC' * num_ac
	if not s or s[0] != inicio:
		s = inicio + s
	if len(s) > tamanho or (len(s) == tamanho and s[-1] != fim):
		return ''
	s += fim * (tamanho - len(s))
	return s
a = [0] * 51
a[1] = 1
b = [0] * 51
b[2] = 1
for i in range(3, 51):
	a[i] = a[i - 2] + a[i - 1]
	b[i] = b[i - 2] + b[i - 1]
for letters in itertools.product(['A', 'B', 'C'], repeat=4):
	first_s1 = letters[0]
	last_s1 = letters[1]
	first_s2 = letters[2]
	last_s2 = letters[3]
	c = [0] * 51
	meio = last_s1 + first_s2
	c[3] = 1 if meio == 'AC' else 0
	for i in range(4, 51):
		meio = last_s2 + (first_s1 if i % 2 == 0 else first_s2)
		c[i] = c[i - 2] + c[i - 1] + (1 if meio == 'AC' else 0)
	for occ1 in range(0, 51):
		tmp = x - a[k] * occ1 - c[k]
		if tmp % b[k] != 0:
			continue
		tmp = tmp // b[k]
		if tmp < 0 or tmp > 50:
			continue
		s1 = valid(first_s1, last_s1, n, occ1)
		s2 = valid(first_s2, last_s2, m, tmp)
		if s1 and s2:
			print(s1)
			print(s2)
			sys.exit(0)
print('Happy new year!')


import sys

def make_string(k, k2string, s1, s2):
	if k in k2string:
		return k2string[k]
	if k == 1:
		k2string[k] = s1
	elif k == 2:
		k2string[k] = s2
	else:
		k2string[k] = make_string(k - 2, k2string, s1, s2) + make_string(k - 1, k2string, s1, s2)
	return k2string[k]

def count_comb(k, k2comb):
	if k in k2comb:
		return k2comb[k]
	if k == 1:
		k2comb[k] = ([0, 0, 0, 0, 1, 0], ('1', '1'))
	elif k == 2:
		k2comb[k] = ([0, 0, 0, 0, 0, 1], ('2', '2'))
	else:
		r_2 = count_comb(k - 2, k2comb)
		r_1 = count_comb(k - 1, k2comb)
		r = ([x + y for (x, y) in zip(r_2[0], r_1[0])], (r_2[1][0], r_1[1][1]))
		ss = r_2[1][1] + r_1[1][0]
		if ss == '11':
			r[0][0] += 1
		elif ss == '12':
			r[0][1] += 1
		elif ss == '21':
			r[0][2] += 1
		elif ss == '22':
			r[0][3] += 1
		k2comb[k] = r
	return k2comb[k]

def max_independent_ac(l, cStart, aEnd):
	if l <= 1:
		return 0
	elif cStart and (not aEnd) or (not cStart and aEnd):
		return (l - 1) // 2
	elif cStart and aEnd:
		return (l - 2) // 2
	else:
		return l // 2

def print_sequence(l, ac, cStart, aEnd):
	cStart = 1 if cStart else 0
	aEnd = 1 if aEnd else 0
	if cStart:
		print('C', end='')
	for i in range(ac):
		print('AC', end='')
	for i in range(l - 2 * ac - cStart - aEnd):
		print('B', end='')
	if aEnd:
		print('A', end='')
	print()

def run_test(k, x, n, m):
	comb = count_comb(k, {})[0]
	for mask in range(16):
		v = [0, 0, 0, 0, 0, 0]
		if mask & 1 and mask & 2:
			v[0] = 1
		if mask & 2 and mask & 4:
			v[1] = 1
		if mask & 1 and mask & 8:
			v[2] = 1
		if mask & 4 and mask & 8:
			v[3] = 1
		if n == 1 and v[0] or (m == 1 and v[3]):
			continue
		max1 = max_independent_ac(n, mask & 1, mask & 2)
		max2 = max_independent_ac(m, mask & 4, mask & 8)
		for p in range(max1 + 1):
			for q in range(max2 + 1):
				v[4] = p
				v[5] = q
				if sum([x * y for (x, y) in zip(v, comb)]) == x:
					print_sequence(n, p, mask & 1, mask & 2)
					print_sequence(m, q, mask & 4, mask & 8)
					return
	print('Happy new year!')
(k, x, n, m) = (int(x) for x in sys.stdin.readline().split(' '))
run_test(k, x, n, m)


def f(k):
	if k == 1:
		return (1, 0, 0, 0, 0)
	if k == 2:
		return (0, 1, 0, 0, 0)
	if k == 3:
		return (1, 1, 1, 0, 0)
	(a, b) = (1, 1)
	for i in range(k - 3):
		(a, b) = (b, a + b)
	c = a
	d = e = 0
	for i in range(k - 3):
		(d, e) = (e, d + e + int(i % 2 == 0))
	return (a, b, c, d, e)

def r(a, i, n):
	if n == 1:
		if a == 'BB':
			return 'B'
		if a == 'BA':
			return 'A'
		if a == 'CB':
			return 'C'
		return False
	if i == 0:
		if a == 'BB':
			return 'B' * n
		if a == 'BA':
			return 'B' * (n - 1) + 'A'
		if a == 'CB':
			return 'C' + 'B' * (n - 1)
	x = 'AC' * i
	n -= len(x)
	if n < 0:
		return False
	if a[0] == 'B':
		if a[1] == 'B':
			return x + 'C' * n
		return x + 'A' * n
	else:
		if a[1] == 'B':
			return 'C' * n + x
		n -= 1
		if n < 1:
			return False
		return 'C' + x + 'A' * n

def g(a, b, i, j, n, m):
	(x, y) = (r(a, i, n), r(b, j, m))
	if x and y:
		print(x)
		print(y)
		return True
	return False

def h():
	(k, x, n, m) = map(int, input().split())
	t = f(k)
	for i in range(n // 2 + 1):
		for j in range(m // 2 + 1):
			if x == t[0] * i + t[1] * j:
				print('AC' * i + 'B' * (n - 2 * i))
				print('AC' * j + 'B' * (m - 2 * j))
				return
	for i in range((n + 1) // 2):
		for j in range((m + 1) // 2):
			y = x - (t[0] * i + t[1] * j)
			if y == t[2] and g('BA', 'CB', i, j, n, m):
				return
			if y == t[3] and g('BB', 'CA', i, j, n, m):
				return
			if y == t[4] and g('CB', 'BA', i, j, n, m):
				return
			if y == t[2] + t[3] and g('BA', 'CA', i, j, n, m):
				return
			if y == t[3] + t[4] and g('CB', 'BA', i, j, n, m):
				return
			if y == t[2] + t[3] + t[4] and g('CA', 'CA', i, j, n, m):
				return
	print('Happy new year!')
h()


def F(a, b, c, d, e, f, k):
	for _ in range(k - 2):
		(a, b, c, d, e, f) = (d, e, f, a, b + e + (c and d), f)
	return e
(k, x, n, m) = map(int, input().split())
for a in [True, False]:
	for c in [True, False]:
		for b in range((n - a - c) // 2 + 1):
			for d in [True, False]:
				for f in [True, False]:
					for e in range((m - d - f) // 2 + 1):
						if F(a, b, c, d, e, f, k) == x:
							print(['', 'C'][a] + 'AC' * b + 'Z' * (n - a - b - b - c) + ['', 'A'][c])
							print(['', 'C'][d] + 'AC' * e + 'Z' * (m - d - e - e - f) + ['', 'A'][f])
							exit()
print('Happy new year!')


(k, x, n, m) = map(int, input().split())

def calc(k, a, b, op1, ed1, op2, ed2):
	if k == 2:
		return b
	return calc(k - 1, b, a + b + (ed1 & op2), op2, ed2, op1, ed2)

def make(len, a, op, ed):
	(res, i) = ('', 0)
	if op:
		res += 'C'
		i += 1
	if ed:
		len -= 1
	while a:
		res += 'AC'
		a -= 1
		i += 2
	while i < len:
		res += 'P'
		i += 1
	if ed:
		res += 'A'
	return res

def check(a, b, op1, ed1, op2, ed2):
	if 2 * a + op1 + ed1 > n or 2 * b + op2 + ed2 > m:
		return 0
	if calc(k, a, b, op1, ed1, op2, ed2) == x:
		print(make(n, a, op1, ed1))
		print(make(m, b, op2, ed2))
		return 1
flag = 0
for i in range(0, (n >> 1) + 1):
	for j in range(0, (m >> 1) + 1):
		for l in range(0, 16):
			if check(i, j, l & 1, l >> 1 & 1, l >> 2 & 1, l >> 3 & 1):
				flag = 1
				break
		if flag:
			break
	if flag:
		break
if not flag:
	print('Happy new year!')