Таємна Книга
Багато організаторів математичних конкурсів зауважують, що їхні учні не дуже добре справляються з так званими двоетапними задачами, які можна розв'язати, послідовно вирішивши два слабко пов'язані підзадачі. Насправді, їм легше вирішити одноетапну задачу, яка є набагато складнішою, ніж обидві підзадачі двоетапної задачі. Тепер у вас є книга з анотацією на обкладинці, яка говорить, що ця книга містить пояснення таємниці цього парадоксу. На жаль, книга заблокована спеціальним замком, але є детальна інструкція, як його відкрити.
Замок складається з двох стрічок з надрукованими на них великими латинськими літерами. Усі літери на обох стрічках мають однакову ширину. Друга стрічка розташована безпосередньо під першою, і вони вирівняні по лівому краю. Щоб краще зрозуміти це, можна уявити ці стрічки як два рядки літер, надруковані моноширинним шрифтом, один під іншим. Довжина другої стрічки (рядка) строго менша за довжину першої. Використовуючи механізм замка, ви можете зсунути будь-яку стрічку вліво або вправо на одну літеру. Цей зсув є циклічним, тобто після зсуву вліво рядок "ABRA" стає "BRAA". Щоб відкрити замок, ви повинні зсунути другу стрічку так, щоб лексикографічний порядок отриманого рядка був якомога меншим. Після цього ви повинні зсунути першу стрічку таким чином, щоб початок першого рядка збігався з усім другим рядком. Наприклад, припустимо, що на першій стрічці міститься рядок "KADAABRA", а на другій стрічці міститься "ABRA". На першому кроці ми повинні зсунути другий рядок на одну літеру вправо, щоб отримати "AABR" (лексикографічно найменший зсув рядка "ABRA"). Після цього ми зсуваємо перший рядок на три літери вліво, отримуючи рядок "AABRAKAD", який починається з "AABR". Крім того, механізм замка приймає комбінації, де будь-яка одна літера у другому рядку відрізняється від відповідної літери у першому рядку. Таким чином, якщо перший рядок "KADABRA", а другий "AABR", допустимо зсунути перший рядок, щоб отримати "DABRAKA", який починається з "DABR", що відрізняється від "AABR" на одну літеру, і замок буде відкрито.
Дані рядки на двох стрічках, знайдіть спосіб відкрити замок. Гарантовано, що рішення існує.
Вхідні дані
Перша строка введення містить два цілі числа N і M, які вказують кількість літер на першій і другій стрічках відповідно (1 ≤ M < N ≤ 1000000). Друга строка складається з N великих латинських літер — рядок, надрукований на першій стрічці. Третя строка складається з M великих латинських літер — рядок, надрукований на другій стрічці.
Вихідні дані
Виведіть два рядки. Перша строка повинна містити отриманий рядок на другій стрічці. Друга строка повинна містити отриманий рядок на першій стрічці. Якщо можливо кілька рішень, виведіть рішення, яке зсуває першу стрічку мінімальну кількість разів. Якщо все ще існує більше одного рішення, виведіть рішення, де перша стрічка зсувається вліво.