Підрядки
[http://ru.wikipedia.org/wiki/Биоинформатика] З моменту секвенування фага Phi-X174 у 1977 році, послідовності ДНК все більшої кількості організмів були розшифровані та збережені в базах даних. Ці дані використовуються для визначення послідовностей білків та регуляторних ділянок. Порівняння генів у межах одного або різних видів може виявити схожість функцій білків або родинні зв'язки між видами (що дозволяє створювати філогенетичні дерева). Зі збільшенням обсягу даних стало неможливим вручну аналізувати послідовності. Сьогодні для пошуку по геномах тисяч організмів, що складаються з мільярдів пар нуклеотидів, використовуються комп'ютерні програми. Ці програми можуть точно вирівнювати схожі послідовності ДНК у геномах різних видів; часто такі послідовності виконують схожі функції, а відмінності виникають через дрібні мутації, такі як заміни окремих нуклеотидів, вставки нуклеотидів, і їх "випадіння" (делеції). Один з варіантів такого вирівнювання застосовується під час самого процесу секвенування. Так звана техніка "дробного секвенування" (яка була, наприклад, використана Інститутом Генетичних Досліджень для секвенування першого бактеріального геному, Haemophilus influenzae) замість повної послідовності нуклеотидів дає послідовності коротких фрагментів ДНК (кожен довжиною близько 600-800 нуклеотидів). Кінці фрагментів накладаються один на одного і, суміщені належним чином, дають повний геном. Такий метод швидко дає результати секвенування, але складання фрагментів може бути досить складним завданням для великих геномів. У проекті з розшифровки геному людини складання зайняло кілька місяців комп'ютерного часу. Зараз цей метод застосовується для практично всіх геномів, і алгоритми складання геномів є однією з найактуальніших проблем біоінформатики на сьогоднішній день.
Вхідні дані
Задано n рядків, кожен з яких має однакову довжину l. Ці рядки містять лише символи англійського алфавіту [A - Z, a - z] (2 ≤ n ≤ 100 000, 2 ≤ l ≤ 100 000). При цьому малі та великі літери вважаються різними символами. Для зменшення витрат на введення/виведення в тестах до задачі n × l ≤ 5 × 1 024 × 1 024.
Вихідні дані
Виведіть рядок довжини l + n - 1, такий, що всі задані у вході рядки є його підрядками, які починаються з різних позицій. Гарантується, що такий рядок існує. Якщо можливі кілька відповідей, виведіть будь-яку.