Tasks:
 
Task DescriptionDiscussion (0)
Task :: 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.

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.

INPUT:
The 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>).

OUTPUT:
To 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:
B 3 2

Output:
010


Explanation:
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:
D 1 1

Output:
impossible


Explanation:
It is not possible to get in D in only one move.
Submit Solution
:
:
Available Languages
Task info
Name:z-01paths
Time:0.05 sec.
Memory:4 MB
#Tests:25
AddedBy: boba5551
Source:Slobodan Mitrović
Task Ratings
Difficulty:

3.1 (15 votes)
Quality:

3.8 (13 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
nemanja1990 0.002 s.
veljkovranic 0.003 s.
eordano 0.004 s.
halil 0.005 s.
picsel 0.006 s.
fushar 0.006 s.
MarioYC 0.006 s.
oduleodule 0.006 s.
ayakut 0.006 s.
zDule98 0.006 s.
Solved By