Preparing NOJ

Getting in Shape

0ms 0K

Description:

Juan decided to start working out and is willing to prepare a workout session.

He knows that some days he might not want to do all exercises from his workout session. He decided on some rules to avoid skipping the whole session and not exercising at all, while still allowing him to optionally skip some exercises.

The rules are:

  • There will be only two types of exercises: $$$A$$$ and $$$B$$$.
  • After finishing an exercise of type $$$B$$$ he moves to the next exercise, if there is one. Otherwise, the workout session ends.
  • After finishing an exercise of type $$$A$$$ there are two possibilities: he can move to the next exercise, or he can skip the next exercise and move to the one after that.
  • The last exercise in a workout session must always be of type $$$B$$$.

Therefore, there might be different ways in which the workout session can be completed. For example, if the types of exercises in a workout session are $$$\texttt{BAAB}$$$, there are 3 ways in which the session can be completed: by doing all exercises, by skipping the 3rd one or by skipping the last one.

Juan wants to prepare his workout session in such a way that there are exactly $$$N$$$ different ways in which the workout session can be completed. Can you help him?

Input:

One positive integer $$$N$$$ ($$$2 \leq N \leq 10^{15}$$$), representing the number of ways in which the workout session can be completed.

Output:

Output a line containing a string, formed only with characters 'A' and 'B', representing the types of the exercises in the workout session. If there are multiple valid answers, output the lexicographically smallest answer. If there is no valid workout sessions, output a line containing the string "IMPOSSIBLE" (without quotes).

Sample Input:

2

Sample Output:

AB

Sample Input:

4

Sample Output:

ABAB

Sample Input:

7

Sample Output:

IMPOSSIBLE

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021-2022 ACM-ICPC Brazil Subregional Programming Contest

Code GYM103388G

Tags

Submitted 7

Passed 1

AC Rate 14.29%

Date 11/01/2021 22:23:43

Related

Nothing Yet