Инопланетный словарь
В далёком будущем земляне обнаружили планету, на которой когда-то жили неизвестные разумные существа. Хотя сами существа не были найдены, их библиотека с множеством письменных материалов была обнаружена. Учёные сразу же начали расшифровку этих материалов, надеясь выяснить, где находятся эти существа.
Анализ текстов показал, что в инопланетной системе письма используется алфавит из N букв, и каждое слово состоит из M букв. Учёные нашли нечто похожее на словарь, который может значительно помочь в изучении этого языка. Слова в этом словаре упорядочены не по лексикографическому принципу, а по убыванию "важности". Если "важность" двух слов одинакова, то раньше записано лексикографически меньшее слово.
Для произвольного слова a_1a_2...a_M "важность" вычисляется следующим образом.
Рассмотрим пример. При N = 2 (количество букв) и M = 3 (длина слова) в этом языке возможно 8 различных слов. Запишем эти слова в лексикографическом порядке. Обозначим k-ю букву инопланетного алфавита k-й буквой латиницы: aaa, aab, aba, abb, baa, bab, bba и bbb. Пусть матрица имеет следующий вид:
Тогда важность слов будет следующей:
aaa: 8 = 1 + 5 + 2;
aab: 12 = 1 + 5 + 6;
aba: 10 = 1 + 7 + 2;
abb: 14 = 1 + 7 + 6;
baa: 12 = 5 + 5 + 2;
bab: 16 = 5 + 5 + 6;
bba: 14 = 5 + 7 + 2;
bbb: 18 = 5 + 7 + 6,
а в словаре порядок слов такой: bbb, bab, abb, bba, aab, baa, aba, aaa.
Для дальнейшего анализа учёным необходимо быстро определять, какое слово будет находиться на определённой позиции в таком словаре согласно описанным правилам упорядочивания: сначала по убыванию "важности", а при одинаковой "важности" — в алфавитном порядке.
По заданным N, M, K и матрице p_jc определите, какое слово будет стоять на K-м месте в словаре инопланетных существ.
Входные данные
Первая строка файла содержит три целых числа: N, M и K. Строки со 2-й до (M+1)-й содержат по N целых чисел — соответствующие элементы матрицы p_jc (2 ≤ N ≤ 16, 1 ≤ M ≤ 10, 0 ≤ p_j_c ≤ 10^8, 1 ≤ K ≤ N^M).
Выходные данные
Единственная строка файла должна содержать слово, которое расположено на K-м месте в словаре инопланетных существ.