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

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: aliens.in
Вихідний файл: aliens.out
Програма: aliens.*

      У віддаленому майбутньому землянами було знайдено планету, на якій раніше жили невідомі людству розумні істоти. Самих істот знайти не вдалося, але було знайдено їхню бібліотеку з великою кількістю писемних матеріалів. Вчені негайно приступили до розшифровування цих матеріалів, сподіваючись зрозуміти, де, власне, самі істоти.
      Аналіз наявних текстів встановив, що в іншопланетній системі письма використовують абетку з N літер, а кожне слово містить M літер. Вчені знайшли щось схоже на словник, який має значно допомогти в розумінні цієї мови. Слова в цьому словнику упорядковано не в лексикографічному порядку, а в порядку спадання «важливості». Якщо «важливість» двох слів однакова, то раніше записано лексикографічно менше слово.
      Для довільного слова a₁ a₂... 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-му місці у словнику іншопланетних істот.

      Обмеження:

• в усіх тестах 2 ≤ N ≤ 16, 1 ≤ M ≤ 10, 0 ≤ p_jc ≤ 10⁸, 1 ≤ K ≤ N ^M;
• у 15% тестів K ≤ 1000;
• ще у 15% тестів M ≤ 5;
• ще в 10% тестів M ≤ 5 і K ≤ 10 одночасно.

      Вхідні дані
      Перший рядок файлу містить три цілі числа: N, M і K. Рядки з 2-го до (M + 1)-го містять по N цілих чисел — відповідні елементи матриці p_jc.

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

      Приклад

2. Симетричні візерунки

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 Mб
Вхідний файл: symmetry.in
Вихідний файл: symmetry.out
Програма: symmetry.*

      У місцях імовірної посадки іншопланетних космічних кораблів іноді знаходять симетричні візерунки, відомі як «кола на полях». Інколи такі візерунки підробляють жартівники. Звичайно, люди не можуть досягти того рівня симетрії, який мають справжні «кола на полях». Тому підробку можна викрити. На одному полі було помічено два візерунки. Для перевірки їхньої справжності ці візерунки сфотографували. На знімку через центри візерунків провели пряму, а на цій прямій відмітили точки, що належать візерункам. Достеменно не відомо, які точки належать якому візерунку. Але можна бути певним, що на проведеній прямій усі точки одного візерунка лежать по один бік від усіх точок іншого візерунка.

      Завдання
      Напишіть програму, яка визначить, чи можна множину відмічених точок розділити на дві непорожні підмножини, кожна з яких симетрична і одна з яких лежить строго лівіше від іншої.

      Вхідні дані
      У першому рядку вхідного файлу вказана кількість тестів T, яка дорівнює 1 або 2. Кожен тест описаний у окремому рядку. На початку кожного рядка стоїть ціле число N (1 ≤ N ≤ 100 000) — кількість точок на прямій для даного тесту. Далі йдуть N різних цілих чисел x₁, x₂, ..., x_N — координати точок на прямій. Відомо, що 0 ≤ x₁ < x₂ < … < x_N ≤ 2⋅10⁹. Числа у рядку розділено пропусками.

      Вихідні дані
      Для кожного з T тестів виведіть відповідь в окремому рядку. Якщо в даному тесті множину точок можна розбити на дві непорожні симетричні множини так, що всі точки однієї множини лежать по один бік від усіх точок іншої, виведіть кількість точок у множині з меншими координатами. Якщо можливі кілька відповідей, виведіть найменшу натуральну з можливих. Якщо розбиття не існує, виведіть 0.

      Приклади