Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D1T3. $\texttt{3s,0.5G}$.

Loves small circles!

Problem Description

$N$ OIers are wearing either red or white hats. Each person can only see the colors of others' hats and will guess the color of their own hat based on the colors of others' hats.

Small circle wants to invite them to dinner, provided that the following conditions are met:

• Let $b$ be the number of people wearing white hats, at least $\lfloor\frac{b}{2}\rfloor$ of them must guess their hat color correctly.
• Let $c$ be the number of people wearing red hats, at least $\lfloor\frac{c}{2}\rfloor$ of them must guess their hat color correctly.

The OIers all want to have dinner with small circle. Help them find a strategy that ensures they can have dinner with small circle in all $2^N$ possible scenarios.

Input Format

A single line containing an integer $N$.

Output Format

Output $N$ lines, each containing a string of length $2^{N-1}$ consisting of characters $\texttt{B}$ and $\texttt{C}$.

The string on the $i$-th line describes the strategy of the $i$-th OIer. Specifically:

• Define $f(S)$ as: the rank of $S$ when all strings of length $(N-1)$ consisting of $\texttt{B}$ and $\texttt{C}$ are sorted lexicographically.
• Let $x$ be the string output on the $i$-th line, and $s_i \in \{\texttt{B},\texttt{C}\}$ be the color of the hat worn by the $i$-th OIer. Here, $\texttt{B}$ represents white (Croatian "bijela"), and $\texttt{C}$ represents red (Croatian "crvena").
• Let $y = \overline{s_1s_2\cdots s_{i-1}s_{i+1}\cdots s_n}$. Note that the left side is the higher bit.
• The $i$-th OIer will guess the color as $x_{f(y)}$.

Refer to the Sample Explanation for details.

Sample Input and Output

Sample Input #1

2

Sample Output #1

BC
CC

Sample Input #2

3

Sample Output #2

BBCC
BCBC
BBCC

Notes

Sample Explanation

Taking Sample #2 as an example.

When $s = \texttt{CCC}$, for the first OIer, $x = \texttt{BBCC}$, $y = \texttt{CC}$. Clearly, $f(y) = 4$, so he will guess $x_4 = \texttt{C}$.

Scoring Method

见题面 Input 部分

见题面 Output 部分