ABC

Write a program to find a string of N characters, where each character can be either "A", "B", or "C". The string must be constructed such that no two adjacent substrings are identical.

For instance, in a string of 7 characters like "ABACBAB", there are no identical adjacent substrings. However, strings such as "ABAACAB", "CABABCA", "CABACAB", and "BACBCBBA" do contain identical adjacent substrings.

Input

The input consists of a single line containing one number: the length of the string N (1 ≤ N ≤ 75).

Output

Output the solution to the problem, or print "No solution" if such a string cannot be constructed. If a solution is possible, provide the lexicographically smallest one.

Examples