Задача: МАРШРУТЫ

В государстве Чудаков N городов ( 2 <=N <= 16 ), обозначаемых заглавными латинскими буквами, начиная с A, по порядку. Между некоторыми из них проложены дороги, которые могут быть как односторонними, так и двусторонними, причем не обязательно, что из каждого города можно проехать в любой другой.

В государстве всего один маршрут автобуса – 'Ч', который совершает только один рейс каждый день. Выходя из некоторого города, он совершает ровно N переездов между городами так, чтобы вернуться в тот, из которого выехал. Других ограничений на его маршрут нет. В течение дня автобус может несколько раз проезжать один и тот же город или дорогу. В каждом городе существуют автобусные парки, из которых могут выезжать автобусы маршрута 'Ч'. Так что, хотя автобус каждый день возвращается в город, из которого стартовал в этот день, на следующий день начало маршрута 'Ч' может быть из любого другого города. Но рейс каждый день только один.

Маршрут обозначается N буквами, начиная с города, из которого происходит выезд. Например, BCDCE – допустимый маршрут для государства из 5 городов ссоответствующими дорогами: выехать из B, проехать в C, затем в D, вернуться в C, проехать в E и вернуться в изначальный город B (последний пункт маршрута, совпадающий с первым, в маршруте не указывается).

Маршрут автобуса меняется каждый день так, что список маршрутов по дням расположен в словарном порядке и содержит все возможные маршруты. Когда список кончается, его обход начинается сначала. В первый день введения маршрута 'Ч' автобус шёл по первому по порядку маршруту. Выведите его маршрут на день K работы маршрута. Пример: В государстве четыре города: A, B, C, D. Наличие дорог между ними задано матрицей, где элемент равен 1, если из города, соответствующего строке, в город, соответствующий столбцу, есть дорога, и 0 – иначе (на главной диагонали нули – дорог, ведущих назад в тот же город, не бывает).

 

откуда/куда	A	B	C	D
A	0	0	1	1
B	1	0	1	1
C	0	1	0	0
D	0	1	1	0

Полное расписание маршрутов в таком государстве выглядит так:
ADCB
BADC
BCBC
BCBD
BDBC
BDBD
CBAD
CBCB
CBDB
DBCB
DBDB
DCBA

Таким образом, например, маршрут на день 30 – это BDBD.

Формат входных данных
В первой строке указывается количество городов N ( 2<= N <= 16 ). Далее следует N строк по N элементов (цифр), разделенных пробелом, содержащих матрицу, задающую дороги между городами. Далее следует строка содержащая целое число D – номер дня, маршрут которого требуется определить ( 1<= D <= 2⁶⁴ ).

Формат выходных данных
В единственной строке указывается маршрут, т.е. порядок посещения городов, например BDBD (см. предыдущий пример).
 

Ввод	Вывод
3 0 1 1 1 0 1 1 1 0 4	BCA

 

           

Ваш ответ: