eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Іншопланетний словник

Іншопланетний словник

Ліміт часу 14 секунд
Ліміт використання пам'яті 64 MiB

У віддаленому майбутньому землянами було знайдено планету, на якій раніше жили невідомі людству розумні істоти. Самих істот знайти не вдалося, але було знайдено їхню бібліотеку з великою кількістю писемних матеріалів. Вчені негайно приступили до розшифровування цих матеріалів, сподіваючись зрозуміти, де, власне, самі істоти.

Аналіз наявних текстів встановив, що в іншопланетній системі письма́ викорис­то­ву­ють абетку з 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 (2N16, 1M10, 0p_j_c10^8, 1KN^M).

Вихідні дані

Єдиний рядок файлу має містити слово, яке розташоване на K-му місці у словнику іншопланетних істот.

Приклад

Вхідні дані #1
2 3 4
1 5
5 7
2 6
Вихідні дані #1
bba