Наскоро на Ели толкова й доскуча в часа по биология, че тя даже реши да слуша учителката. Изненадващо, урокът й се стори много интересен. В него ставаше дума за Дезоксирибонуклеиновата киселина, също позната като ДНК. Чрез нея човешкото тяло "помни" генетична информация – или по-конкретно как да създава различни видове клетки. Част от тази информация са така наречените "гени", които определят колко висок, красив, здрав, а, според някои теории, и умен е човек.

ДНК кодира генетичната информация благодарение на четири „строителни елемента“, наречени бази: аденин ('A'), тимин ('T'), гуанин ('G'), и цитозин ('C'). В много прост вариант можем да си представим ДНК-то като последователност от тези елементи, или като стринг, съставен от тези четири букви.

Човешкият организъм явно има мотото "повторението е майка на знанието", тъй като за да "запомни" по-сигурно тази информация той повтаря части от ДНК-то отново и отново. Така дори някоя от частите да бъде нарушена по някаква причина, останалите копия ще могат да бъдат ползвани за нейното възстановяване. Сега Ели се чуди, дали генното инженерство ще й помогне да намери Перфектния Мъж. Тъй като самата тя е перфектна (поне по нейно мнение), Ели реши да сравнява своето ДНК с това на всеки потенциален кандидат. Като част от този процес тя трябва да намери най-дългата част от своето ДНК, която се среща в това на кандидата поне K пъти. Помогнете ѝ, като напишете програма, която прави това.

Накратко, дадени са ви два стринга S₁ и S₂. От вас се иска да намерите най-дългия подстринг на S₁, който се среща като подстринг в S₂ поне K пъти. Забележете, че за целите на момичето е разрешено тези K срещания да се припокриват частично. Също така забележете, че подстрингът не е задължително да се среща в S₁ повече от веднъж (но е задължително да се среща в S₂ поне K пъти). На първия ред на стандартния вход ще бъдат зададени три цели числа: N, M, и K – съответно дължината на ДНК-то на Ели, дължината на ДНК-то на кандидата, и константата K. На втория ред ще бъде зададен S₁ - стринг с N букви от азбуката {'A', 'T', 'G', 'C'}. На третия ред ще бъде зададен S₂ – стринг с M букви от същата азбука. На единствен ред на стандартния изход изведете най-дългия стринг, който отговаря на горните условия. Ако съществуват няколко възможности, изведете лексикографски най-малката. Гарантирано е, че ще има поне един непразен такъв стринг.

• 1 ≤ N, M, K ≤ 100,000

Примерен Вход	Примерен Изход
7 18 3 GATTACA CACATACGTACACATACC	ACA