Задачи
Іншопланетний словник
Іншопланетний словник
У віддаленому майбутньому землянами було знайдено планету, на якій раніше жили невідомі людству розумні істоти. Самих істот знайти не вдалося, але було знайдено їхню бібліотеку з великою кількістю писемних матеріалів. Вчені негайно приступили до розшифровування цих матеріалів, сподіваючись зрозуміти, де, власне, самі істоти.
Аналіз наявних текстів встановив, що в іншопланетній системі письма́ використовують абетку з \textbf{N} літер, а кожне слово містить \textbf{M} літер. Вчені знайшли щось схоже на словник, який має значно допомогти в розумінні цієї мови. Слова в цьому словнику упорядковано не в лексикографічному порядку, а в порядку спадання "важливості". Якщо "важливість" двох слів однакова, то раніше записано лексикографічно менше слово.
\includegraphics{https://static.e-olymp.com/content/d2/d20ed3b01ebd0adf64b886e78868d1ca54287336.jpg}
Для довільного слова \textbf{a_1a_2...a_M} цю "важливість" знаходять як .
Розглянемо такий приклад. При \textbf{N = 2} (кількість літер) і \textbf{M = 3} (довжина слова) у цій мові можливі \textbf{8} різних слів. Запишемо ці слова в лексикографічному порядку. Позначатимемо тут і далі \textbf{k}-ту літеру іншопланетної абетки \textbf{k}-ю літерою латиниці: \textbf{aaa}, \textbf{aab}, \textbf{aba}, \textbf{abb}, \textbf{baa}, \textbf{bab}, \textbf{bba} і \textbf{bbb}. Нехай матриця має такий вигляд:
\includegraphics{https://static.e-olymp.com/content/48/4891d0a37a171e404114aa75c88f028e83966011.jpg}
Тоді важливість слів буде такою:
\textbf{aaa: 8 = 1 + 5 + 2;}
\textbf{aab: 12 = 1 + 5 + 6;}
\textbf{aba: 10 = 1 + 7 + 2;}
\textbf{abb: 14 = 1 + 7 + 6;}
\textbf{baa: 12 = 5 + 5 + 2;}
\textbf{bab: 16 = 5 + 5 + 6;}
\textbf{bba: 14 = 5 + 7 + 2;}
\textbf{bbb: 18 = 5 + 7 + 6,}
а у словнику порядок слів такий: \textbf{bbb}, \textbf{bab}, \textbf{abb}, \textbf{bba}, \textbf{aab}, \textbf{baa}, \textbf{aba}, \textbf{aaa}.
Для подальшого аналізу ученим-землянам потрібно вміти швидко обчислювати, яке слово буде міститися на певному місці в такому словнику згідно з описаними правилами впорядкування: спочатку за спаданням "важливості", а при однаковій "важливості" --- у алфавітному порядку.
За відомими \textbf{N}, \textbf{M}, \textbf{K} і матрицею \textbf{p_jc} визначити, яке слово стоятиме на \textbf{K}-му місці у словнику іншопланетних істот.
\InputFile
Перший рядок файлу містить три цілі числа: \textbf{N}, \textbf{M} і \textbf{K}. Рядки з \textbf{2}-го до (\textbf{M+1})-го містять по \textbf{N} цілих чисел --- відповідні елементи матриці \textbf{p_jc} (\textbf{2} ≤ \textbf{N} ≤ \textbf{16}, \textbf{1} ≤ \textbf{M} ≤ \textbf{10}, \textbf{0} ≤ \textbf{p_j_c} ≤ \textbf{10^8}, \textbf{1} ≤ \textbf{K} ≤ \textbf{N^M}).
\OutputFile
Єдиний рядок файлу має містити слово, яке розташоване на \textbf{K}-му місці у словнику іншопланетних істот.
Входные данные #1
2 3 4 1 5 5 7 2 6
Выходные данные #1
bba