There are N cities ( 2 <=N <= 16 ) in the state of Eccentrics, denoted by capital Latin letters, starting with A, in order. Between some of them there are roads that can be either one-way or two-way, and it is not necessary that you can drive from each city to any other.
There is only one bus route in the state – 'W', which makes only one flight every day. Leaving a certain city, he makes exactly N transfers between cities in such a way as to return to the one from which he left. There are no other restrictions on its route. During the day, the bus may pass the same city or road several times. In each city there are bus depots from which buses of the 'H' route can leave. So, although the bus returns every day to the city from which it started that day, the next day the start of the route 'W' could be from any other city. But there is only one flight every day.
The route is indicated by N letters, starting from the city from which the departure takes place. For example, BCDCE – a valid route for a state of 5 cities with corresponding roads: leave B, go to C, then to D, return to C, go to E, and return to the original city B (the last point of the route, which is the same as the first, is not indicated in the route).
The route of the bus changes every day so that the list of routes by day is in dictionary order and contains all possible routes. When the list ends, it starts over from the beginning. On the first day of the introduction of the route 'H' The bus was on the first route. Print its route for day K of the route's operation. Example: There are four cities in the state: A, B, C, D. The presence of roads between them is given by a matrix where the element is equal to 1 if there is a road from the city corresponding to the row to the city corresponding to the column, and 0 – otherwise (there are no zeros on the main diagonal – there are no roads leading back to the same city).
|
from where/where |
A |
B |
C |
D |
|
A |
0 |
0 |
1 |
1 |
|
B |
1 |
0 |
1 |
1 |
|
C |
0 |
1 |
0 |
0 |
|
D |
0 |
1 |
1 |
0 |
The full schedule of routes in such a state looks like this:
ADCB
BADC
BCBC
BCBD
BDBC
BDBD
CBAD
CBCB
CBDB
DBCB
DBDB
DCBA
Thus, for example, the itinerary for day 30 – this is BDBD.
Input data format
The first line contains the number of cities N ( 2<= N <= 16 ). This is followed by N lines of N elements (digits) each, separated by a space, containing a matrix specifying roads between cities. This is followed by a line containing the integer D – the number of the day whose itinerary is to be determined ( 1<= D <= 2
64 ).
Output data format
The single line specifies the route, i.e. the order in which cities are visited, for example BDBD (see previous example).
|
Enter |
Output |
3
0 1 1
1 0 1
1 1 0
4 |
BCA |