z-01paths
Little Z is positioned in one of four a bit strange set of rooms with a teleport machine in each of them. Rooms are named A, B, C and D. In each room there are two buttons, which we will label as 0 and 1. Pressing 0 in the room A teleports you to the room C and vice versa; pressing 0 in the room B teleports you to the room D and vice versa. Pressing 1 in the room A teleports you to the room B and vice versa; pressing 1 in the room C teleports you to the room D and vice versa. These teleports are also shown on the image below.
Image: img1
Pressing exactly n times button 0 or button 1 we will call n-length 01-path. It is obvious that after each n-length 01-path Little Z will end in some room. Little Z would like to finish at some of the four given rooms by pressing buttons 0 and buttons 1. He is interested in K-th lexicographically smallest n-length 01-path such that he ends up in the room R.
Little Z will always start at room A.
InputThe first line of the standard input contains character R, one of the upper-case letters A, B, C or D, and two space-separated integers n (1 <= n <= 50) and K (1 <= K <= 10<sup>9</sup>).
OutputTo the first line of the standard ouput you should print K-th lexicographically smallest n-length 01-path if such exists, else print "impossible" (without quotes).
Input:
Output:
B 3 2Output:
010Explanation:
All possible paths, sorted lexicographically, are: 000, 001, 010, 011, 100, 101, 110 and 111.
Paths 001 (A -> C -> A -> B), 010 (A -> C -> D -> B), 100 (A -> B -> D -> B) and 111 (A -> B -> A -> B) are those that finish at B. Second one is 010.
Input:
Output:
D 1 1Output:
impossibleExplanation:
It is not possible to get in D in only one move.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.