As their act for their school's variety show, Alice and Bob are going to perform their own remix of the classic disco song Dancing Queen! Aside from the chorus, their remix has $N$ different verses to be sung by the two of them.
The verses are labeled $1, 2, 3, \\dots, N$, in sequence. Each verse sung involves more and more _fabulous_ outfits, choreography, pyrotechnics, disco lights, etc. Let's say that the _fabulousness_ of the $k$th verse is exactly equal to $k$. Some of these verses will be performed by Alice, and the others will be performed by Bob. So that one does not overshadow the other, they wish to ensure that the total fabulousness of their verses is as fairly divided as possible.
Formally, let $A$ be the sum of the fabulousness of verses given to Alice, and let $B$ be the sum of the fabulousness of verses given to Bob. Find any way to distribute the verses between the two of them such that $| A -B |$ is minimal.
Input consists of a single line containing a single positive integer $N$.
First, output a line containing a single integer, the minimal value of $| A -B |$.
Then, output a line containing a string of $N$ characters, where the $k$th of these characters is _A_ if the $k$th verse goes to Alice, and _B_ if it goes to Bob. If there are multiple solutions, output any of them.
*Subtask 1:* (40 pts):
$1 <= N <= 15$
*Subtask 2:* (20 pts):
$1 <= N <= 100$
*Subtask 3:* (15 pts):
$1 <= N <= 1000$
*Subtask 4:* (25 pts):
$1 <= N <= 2 dot.op 10^5$
If there are $3$ verses, then we can make $| A -B | = 0$ if we give Alice verses $1$ and $2$ while Bob gets verse $3$.
If there are $10$ verses, then we can prove that $| A -B | = 1$ is the lowest we can make it. In the example, Alice gets verses $2, 3, 4, 5, 6$, and $8$, for a total fabulousness of $28$, while Bob gets verses $1, 7, 9$, and $10$, for a total fabulousness of $27$.
In both cases, it is equally valid if we gave Alice the verses we had given to Bob, and vice versa.
## Input
Input consists of a single line containing a single positive integer $N$.
## Output
First, output a line containing a single integer, the minimal value of $| A -B |$.Then, output a line containing a string of $N$ characters, where the $k$th of these characters is _A_ if the $k$th verse goes to Alice, and _B_ if it goes to Bob. If there are multiple solutions, output any of them.
[samples]
## Scoring
*Subtask 1:* (40 pts):$1 <= N <= 15$*Subtask 2:* (20 pts):$1 <= N <= 100$*Subtask 3:* (15 pts):$1 <= N <= 1000$*Subtask 4:* (25 pts):$1 <= N <= 2 dot.op 10^5$
## Note
If there are $3$ verses, then we can make $| A -B | = 0$ if we give Alice verses $1$ and $2$ while Bob gets verse $3$.If there are $10$ verses, then we can prove that $| A -B | = 1$ is the lowest we can make it. In the example, Alice gets verses $2, 3, 4, 5, 6$, and $8$, for a total fabulousness of $28$, while Bob gets verses $1, 7, 9$, and $10$, for a total fabulousness of $27$.In both cases, it is equally valid if we gave Alice the verses we had given to Bob, and vice versa.
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of verses.
Let $ S = \sum_{k=1}^N k = \frac{N(N+1)}{2} $ be the total fabulousness.
Let $ A \subseteq \{1, 2, \dots, N\} $ be the set of verses assigned to Alice, and $ B = \{1, 2, \dots, N\} \setminus A $ be the set assigned to Bob.
Let $ a = \sum_{k \in A} k $, $ b = \sum_{k \in B} k $, so that $ a + b = S $.
**Constraints**
$ 1 \leq N \leq 2 \times 10^5 $
**Objective**
Minimize $ |a - b| = |2a - S| $, and output any assignment achieving this minimum.
The minimal value of $ |a - b| $ is $ S \bmod 2 $.
If $ S $ is even, then $ |a - b| = 0 $; if $ S $ is odd, then $ |a - b| = 1 $.
Construct a subset $ A $ such that $ a = \lfloor S/2 \rfloor $ using a greedy approach: iterate from $ N $ down to $ 1 $, and assign verse $ k $ to Alice if adding it does not exceed $ \lfloor S/2 \rfloor $.