Codeforces Round 134 (Div. 1)
B
Blackboard Fibonacci
Codeforces
2100
原题
← AC →
翻译中…

Fibonacci numbers are the sequence of integers: $*f*_{0} = 0$, $*f*_{1} = 1$, $*f*_{2} = 1$, $*f*_{3} = 2$, $*f*_{4} = 3$, $*f*_{5} = 5$, $...$, $*f*_{*n*} = *f*_{*n* - 2} + *f*_{*n* - 1}$. So every next number is the sum of the previous two.

翻译中…

Bajtek has developed a nice way to compute Fibonacci numbers on a blackboard. First, he writes a 0. Then, below it, he writes a 1. Then he performs the following two operations:

翻译中…
  • operation "T": replace the top number with the sum of both numbers;
  • operation "B": replace the bottom number with the sum of both numbers.
翻译中…

If he performs $*n*$ operations, starting with "T" and then choosing operations alternately (so that the sequence of operations looks like "TBTBTBTB$...$"), the last number written will be equal to $*f*_{*n* + 1}$.

翻译中…

Unfortunately, Bajtek sometimes makes mistakes and repeats an operation two or more times in a row. For example, if Bajtek wanted to compute $*f*_{7}$, then he would want to do $*n* = 6$ operations: "TBTBTB". If he instead performs the sequence of operations "TTTBBT", then he will have made 3 mistakes, and he will incorrectly compute that the seventh Fibonacci number is 10. The number of mistakes in the sequence of operations is the number of neighbouring equal operations («TT» or «BB»).

翻译中…

You are given the number $*n*$ of operations that Bajtek has made in an attempt to compute $*f*_{*n* + 1}$ and the number $*r*$ that is the result of his computations (that is last written number). Find the minimum possible number of mistakes that Bajtek must have made and any possible sequence of $*n*$ operations resulting in $*r*$ with that number of mistakes.

翻译中…

Assume that Bajtek always correctly starts with operation "T".

翻译中…

Input

翻译中…

The first line contains the integers $*n*$ and $*r*$ ($1 ≤ *n*, *r* ≤ 10^{6})$.

翻译中…

Output

翻译中…

The first line of the output should contain one number — the minimum possible number of mistakes made by Bajtek. The second line should contain $*n*$ characters, starting with "T", describing one possible sequence of operations with that number of mistakes. Each character must be either "T" or "B".

翻译中…

If the required sequence doesn't exist, output "IMPOSSIBLE" (without quotes).

翻译中…

样例

Input #1
6 10
Output #1
2
TBBTTB
InputCopy OutputCopy
Input #2
4 5
Output #2
0
TBTB
InputCopy OutputCopy
Input #3
2 1
Output #3
IMPOSSIBLE
InputCopy OutputCopy
题目信息
题号
217B
时间限制
1 s
内存限制
256 MB
标签
暴力
数学

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。