Bob has painstakingly written pages of solutions for his physics homework. Each page is labelled from to . He has kept them in a pile, but being very disorganized, he ordered them randomly. In particular, the page from the top is page . Now that it's time to hand it in, he has to sort the pile!
Bob takes the top page of the first pile and creates a new pile with it. He then takes the new top page of the first pile and chooses to either place it at the top of the second pile or the bottom. He keeps doing this until all the pages are now in the second pile. Bob defines this series of operations as a single restacking. He performs this restacking with the new pile until he has a sorted pile of the pages.
Given the original pile, can you help Bob sort his physics homework? Bob is busy with other homework, so he asks that your sort takes at most restackings.
Constraints
For all ,
Each number from to will appear exactly once.
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [80%]
Input Specification
The first line will contain two space-separated integers, and .
The next line will contain space-separated integers, .
Output Specification
On the first line, output a single integer , denoting the number of restackings you use. must be between and inclusive.
On the next lines, output a string of characters representing instructions for restacking. Remember that the top page becomes the new pile, leaving pages in the original pile. The character should be T
to move the current top page to the top of the new pile, or B
to move it to the bottom of the new pile.
If these specifications are not satisfied or if your instructions do not sort the pile, you will receive a Wrong Answer
verdict.
Sample Input 1
8 2000
1 5 2 6 3 7 4 8
Sample Output 1
2
BTBTBTB
TTTBBBB
Explanation for Sample 1
After the first set of instructions, the pile becomes
4 3 2 1 5 6 7 8
After the second set of instructions, the pile becomes
1 2 3 4 5 6 7 8
So the pages have been sorted.
Sample Input 2
2 2000
1 2
Sample Output 2
0
Comments