The Central European Olympiad in Informatics (CEOI) is being held in our beautiful country this year. The contestants are extra excited because of the most famous Croatian tradition at informatics olympiads. Of course, it is about gifting hats with a recognizable "checkered" pattern.

However, Mr. Malnar has decided to put an end to another tradition. This year, monochromatic hats, colored red or white, will be distributed. Mr. Malnar did not make this decision lightly; it is part of a carefully thought-out plan.

Specifically, Malnar knows that at some point, $N$ young computer scientists will find themselves in the same place, and each of them will be wearing a red or white hat on their head. Naturally, each computer scientist will see all the hats except their own, and as is customary, they will all simultaneously shout what color they think their hat is.

All computer scientists who guess the color of their hat correctly will go to dinner with Mr. Malnar as a reward. However, Mr. Malnar cares deeply that both hat colors are sufficiently represented at the dinner. He told them that out of all $b$ computer scientists with a white hat, at least $\lceil b/2 \rceil$ of them must guess their color correctly, and out of all $c$ computer scientists with a red hat, at least $\lceil c/2 \rceil$ of them must guess their color correctly; otherwise, he will not take anyone to dinner.

Help the young computer scientists find a strategy that will ensure Mr. Malnar's condition is met for every possible arrangement of hats.

Input

The first and only line contains a natural number $N$, the number of computer scientists.

Output

The computer scientists are labeled with natural numbers from $1$ to $N$. Let $s_i$ be the character representing the color of the $i$-th computer scientist's hat, B for white and C for red.

In the $i$-th line, you must output a string of $2^{N-1}$ characters B and C that describes the strategy of the $i$-th computer scientist. Let us denote this string of characters as $x_i$. The computer scientist will look at the hats of the others and describe the situation they see with the string $y_i = s_1 \dots s_{i-1}s_{i+1} \dots s_N$. Then, they will determine the index $k_i$ of that string among all strings of length $N-1$ consisting of B and C, sorted alphabetically. If the $k_i$-th letter in their strategy $x_i$ is B, they will say "white!", and if it is C, they will say "red!".

For further clarification, see the examples.

Subtasks

Examples

Input 1

2

Output 1

BC
CC

Input 2

3

Output 2

BBCC
BCBC
BBCC

Note

Explanation of the examples:

The first row of the image shows all four possible cases in the first example. The second row of the image shows two possible cases in the second example.

First case: $1 \quad s_1 = \text{C} \quad x_1 = \text{CC} \quad k_1 = 4 \quad \text{C}$ $2 \quad s_2 = \text{C} \implies x_2 = \text{CC} \implies k_2 = 4 \implies \text{C}$ $3 \quad s_3 = \text{C} \quad x_3 = \text{CC} \quad k_3 = 4 \quad \text{C}$

Second case: $1 \quad s_1 = \text{C} \quad x_1 = \text{BB} \quad k_1 = 1 \quad \text{B}$ $2 \quad s_2 = \text{B} \implies x_2 = \text{CB} \implies k_2 = 3 \implies \text{B}$ $3 \quad s_3 = \text{B} \quad x_3 = \text{CB} \quad k_3 = 3 \quad \text{C}$

Figure 1. Explanation of the examples: The first row shows all four possible cases in the first example, and the second row shows two possible cases in the second example.